Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDrawing Graphs on Few Lines and Few Planes
256
0
0.0
(
0
)
Added by
Fabian Lipp
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows. We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values. We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing). We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.
rate research
Read More
It is well known that any graph admits a crossing-free straight-line drawing in $mathbb{R}^3$ and that any planar graph admits the same even in $mathbb{R}^2$. For a graph $G$ and $d in {2,3}$, let $rho^1_d(G)$ denote the minimum number of lines in $mathbb{R}^d$ that together can cover all edges of a drawing of $G$. For $d=2$, $G$ must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results. - For $din{2,3}$, we prove that deciding whether $rho^1_d(G)le k$ for a given graph $G$ and integer $k$ is ${existsmathbb{R}}$-complete. - Since $mathrm{NP}subseteq{existsmathbb{R}}$, deciding $rho^1_d(G)le k$ is NP-hard for $din{2,3}$. On the positive side, we show that the problem is fixed-parameter tractable with respect to $k$. - Since ${existsmathbb{R}}subseteqmathrm{PSPACE}$, both $rho^1_2(G)$ and $rho^1_3(G)$ are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to $rho^1_2$ or $rho^1_3$ sometimes require irrational coordinates. - Let $rho^2_3(G)$ be the minimum number of planes in $mathbb{R}^3$ needed to cover a straight-line drawing of a graph $G$. We prove that deciding whether $rho^2_3(G)le k$ is NP-hard for any fixed $k ge 2$. Hence, the problem is not fixed-parameter tractable with respect to $k$ unless $mathrm{P}=mathrm{NP}$.
A emph{Stick graph} is an intersection graph of axis-aligned segments such that the left end-points of the horizontal segments and the bottom end-points of the vertical segments lie on a `ground line, a line with slope $-1$. It is an open question to decide in polynomial time whether a given bipartite graph $G$ with bipartition $Acup B$ has a Stick representation where the vertices in $A$ and $B$ correspond to horizontal and vertical segments, respectively. We prove that $G$ has a Stick representation if and only if there are orderings of $A$ and $B$ such that $G$s bipartite adjacency matrix with rows $A$ and columns $B$ excludes three small `forbidden submatrices. This is similar to characterizations for other classes of bipartite intersection graphs. We present an algorithm to test whether given orderings of $A$ and $B$ permit a Stick representation respecting those orderings, and to find such a representation if it exists. The algorithm runs in time linear in the size of the adjacency matrix. For the case when only the ordering of $A$ is given, we present an $O(|A|^3|B|^3)$-time algorithm. When neither ordering is given, we present some partial results about graphs that are, or are not, Stick representable.
We show that the asymptotic dimension of a geodesic space that is homeomorphic to a subset in the plane is at most three. In particular, the asymptotic dimension of the plane and any planar graph is at most three.
We initiate the study of the following problem: Given a non-planar graph G and a planar subgraph S of G, does there exist a straight-line drawing {Gamma} of G in the plane such that the edges of S are not crossed in {Gamma} by any edge of G? We give positive and negative results for different kinds of connected spanning subgraphs S of G. Moreover, in order to enlarge the subset of instances that admit a solution, we consider the possibility of bending the edges of G not in S; in this setting we discuss different trade-offs between the number of bends and the required drawing area.
Storyline visualizations show the structure of a story, by depicting the interactions of the characters over time. Each character is represented by an x-monotone curve from left to right, and a meeting is represented by having the curves of the participating characters run close together for some time. There have been various approaches to drawing storyline visualizations in an automated way. In order to keep the visual complexity low, rather than minimizing pairwise crossings of curves, we count block crossings, that is, pairs of intersecting bundles of lines. Partly inspired by the ILP-based approach of Gronemann et al. [GD 2016] for minimizing the number of pairwise crossings, we model the problem as a satisfiability problem (since the straightforward ILP formulation becomes more complicated and harder to solve). Having restricted ourselves to a decision problem, we can apply powerful SAT solvers to find optimal drawings in reasonable time. We compare this SAT-based approach with two exact algorithms for block crossing minimization, using both the benchmark instances of Gronemann et al. and random instances. We show that the SAT approach is suitable for real-world instances and identify cases where the other algorithms are preferable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
