1,720,989 research outputs found
Sketched Representations and Orthogonal Planarity of Bounded Treewidth Graphs
No full textGiven a planar graph G and an integer b, OrthogonalPlanarity is the problem of deciding whether G admits an orthogonal drawing with at most b bends in total. We show that OrthogonalPlanarity can be solved in polynomial time if G has bounded treewidth. Our proof is based on an FPT algorithm whose parameters are the number of bends, the treewidth and the number of degree-2 vertices of G. This result is based on the concept of sketched orthogonal representation that synthetically describes a family of equivalent orthogonal representations. Our approach can be extended to related problems such as HV-Planarity and FlexDraw. In particular, both OrthogonalPlanarity and HV-Planarity can be decided in time for series-parallel graphs, which improves over the previously known bounds
Ortho-polygon visibility representations of 3-connected 1-plane graphs
No full textAn ortho-polygon visibility representation (OPVR) of an embedded graph G is an embedding-preserving drawing that maps each vertex of G to a distinct orthogonal polygon and each edge of G to a vertical or horizontal visibility between its end-vertices. An OPVR Γ has vertex complexity k if every polygon of Γ has at most k reflex corners. A 1-plane graph is an embedded graph such that each edge is crossed at most once. It is known that 3-connected 1-plane graphs admit an OPVR with vertex complexity at most 12, while vertex complexity at least 2 may be required in some cases. In this paper, we reduce this gap by showing that vertex complexity 5 is always sufficient, while vertex complexity 4 may be sometimes required. These results are based on the study of the combinatorial properties of the B-, T-, and W-configurations in 3-connected 1-plane graphs. An implication of the upper bound is the existence of a O ̃(n[Formula presented])-time drawing algorithm that computes an OPVR of an n-vertex 3-connected 1-plane graph on an integer grid of size O(n)×O(n) and with vertex complexity at most 5
Efficient and trustworthy decision making through human-in-the-loop visual analytics: A case study on tax risk assessment | Processi decisionali efficienti e affidabili tramite analisi visuale con metodologia human-in-the-loop: un caso di studio sulla valutazione del rischio fiscale
No full textIl data mining e l'intelligenza artificiale sono sempre più utilizzati nell'analisi dei dati. L'ideale sarebbe ottenere un'automazione completa, ma in molte applicazioni ciò comporta rischi significativi. In questi casi è necessario il coinvolgimento diretto di analisti umani per raffinare l'analisi o per prendere le decisioni finali. Un problema rilevante è quindi come garantire un processo decisionale efficiente e affidabile nel quale gli esseri umani sono parte integrante del processo di analisi. Proponiamo una metodologia human-in-the-loop che sfrutta il data mining, il machine learning, e la visualizzazione per migliorare il processo di analisi. Un elemento chiave è l'uso di una dashboard visuale intuitiva, di supporto all'individuazione di relazioni e pattern di dati nascosti. Come caso di studio, descriviamo un'applicazione di questa metodologia per l'analisi del rischio fiscale nell'ambito delle attività dell’Agenzia delle Entrate.Data mining and AI techniques are increasingly being used to automate data analysis. Ideally, one may wish to completely automate the data analysis process, but in many real-world applications a full automation may pose significant risks. In these cases, human analysts must be directly involved to refine the analysis or to make the final decisions. A challenging problem, therefore, is how to perform efficient and trustworthy decision-making when humans are an integral part of the analysis pipeline. We propose a "human-in-the-loop" methodology that leverages data mining, machine learning, and visual analytics to improve and speed up the analysis. A key feature is the use of a dashboard that integrates intuitive visual tools, which aid analysts to efficiently discover hidden data patterns or to get helpful insights. We describe in particular how this methodology has been successfully applied to support Revenue Agency officers in tax risk assessment
The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable
No full textThe problem of deciding whether a biconnected planar digraph G = (V, E) can be augmented to become an st-planar graph by adding a set of oriented edges E′ ⊆ V ×V is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set E
STRICTLY CONVEX DRAWINGS OF 3-CONNECTED PLANAR GRAPHS
No full textStrictly convex straight-line drawings of 3-connected planar graphs in small area form a classical research topic in Graph Drawing. Currently, the best-known area bound for such drawings of n-vertex graphs is O(n2)×O(n2), as shown by Bárány and Rote by means of a sophisticated technique based on perturbing (non strictly) convex drawings. Unfortunately, the constants hidden in this area bound are in the order of 104. We present a new and easy-to-implement technique that yields strictly convex straight-line planar drawings of 3-connected planar graphs on an integer grid of size 2(n − 1) × (2n3 − n2)
Parameterized Algorithms for Queue Layouts
No full textAn h-queue layout of a graph G consists of a linear order of its vertices and a partition of its edges into h sets, called queues, such that no two independent edges of the same queue nest. The minimum h such that G admits an h-queue layout is the queue number of G. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph G has queue number 1 and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of G. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary h
ChordLink: A New Hybrid Visualization Model
No full textMany real-world networks are globally sparse but locally dense. Typical examples are social networks, biological networks, and information networks. This double structural nature makes it difficult to adopt a homogeneous visualization model that clearly conveys an overview of the network and the internal structure of its communities at the same time. As a consequence, the use of hybrid visualizations has been proposed. For instance, NodeTrix combines node-link and matrix-based representations (Henry et al., 2007). In this paper we describe ChordLink, a hybrid visualization model that embeds chord diagrams, used to represent dense subgraphs, into a node-link diagram, which shows the global network structure. The visualization is intuitive and makes it possible to interactively highlight the structure of a community while keeping the rest of the layout stable. We discuss the intriguing algorithmic challenges behind the ChordLink model, present a prototype system, and illustrate case studies on real-world networks
Crossing Numbers of Beyond-Planar Graphs
No full textWe study the 1-planar, quasi-planar, and fan-planar crossing number in comparison to the (unrestricted) crossing number of graphs. We prove that there are n-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has crossings, while O crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns
Parameterized algorithms for book embedding problems
No full textA k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether G admits a k-page book embedding both when the linear order of the vertices is fixed, called Fixed-Order Book Thick-ness, or not fixed, called Book Thickness. Both problems are known to be NP-complete in general. We show that Fixed-Order Book Thickness and Book Thickness are fixed-parameter tractable parameterized by the vertex cover number of the graph and that Fixed-Order Book Thickness is fixed-parameter tractable parameterized by the pathwidth of the vertex order
Crossing numbers of beyond-planar graphs
No full textWe study the 1-planar, quasi-planar, and fan-planar crossing number in comparison to the (unrestricted) crossing number of graphs. We prove that there are n-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has Ω(n) crossings, while O(1) crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns
- …
