Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
From MaRDI portal
(Redirected from Publication:904086)
Abstract: 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.
Recommendations
- Drawing non-planar graphs with crossing-free subgraphs
- Large angle crossing drawings of planar graphs in subquadratic area
- Mathematical programs for drawing nonplanar graphs in the plane
- Area, curve complexity, and crossing resolution of non-planar graph drawings
- Area, curve complexity, and crossing resolution of non-planar graph drawings
Cites work
- scientific article; zbMATH DE number 2123123 (Why is no real title available?)
- A sufficient condition for the existence of plane spanning trees on geometric graphs
- Advancements on SEFE and partitioned book embedding problems
- Applications of the crossing number
- Area requirement of graph drawings with few crossings per edge
- Configurations with few crossings in topological graphs
- Density of straight-line 1-planar graph drawings
- Drawing graphs with right angle crossings
- Drawing planar graphs using the canonical ordering
- Fáry's theorem for 1-planar graphs
- Graphs drawn with few crossings per edge
- How to draw a planar graph on a grid
- Noncrossing Subgraphs in Topological Layouts
- On geometric graphs with no k pairwise parallel edges
- On the density of maximal 1-planar graphs
- On the maximum number of edges in quasi-planar graphs
- On the maximum number of edges in topological graphs with no four pairwise crossing edges
- Short path queries in planar graphs in constant time
- Strictly convex drawings of planar graphs
- Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)
- Testing simultaneous planarity when the common graph is 2-connected
- Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
- The complexity of detecting crossingfree configurations in the plane
- The crossing-angle resolution in graph drawing
- The number of edges in k-quasi-planar graphs
- h-quasi planar drawings of bounded treewidth graphs in linear area
Cited in
(10)- Drawing non-planar graphs with crossing-free subgraphs
- Large angle crossing drawings of planar graphs in subquadratic area
- Area, curve complexity, and crossing resolution of non-planar graph drawings
- Non-aligned drawings of planar graphs
- scientific article; zbMATH DE number 3646924 (Why is no real title available?)
- Construction of a topological drawing of the most planar subgraph of the non-planar graph
- SOFSEM 2005: Theory and Practice of Computer Science
- Picking planar edges; or, drawing a graph with a planar subgraph
- Area, curve complexity, and crossing resolution of non-planar graph drawings
- Non-aligned drawings of planar graphs
This page was built for publication: Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q904086)
