Embedding-preserving rectangle visibility representations of nonplanar graphs
From MaRDI portal
Publication:1991089
Abstract: A rectangle visibility representation (RVR) of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Testing whether a graph has an RVR is known to be NP-hard. In this paper, we study the problem of finding an RVR under the assumption that an embedding in the plane of the input graph is fixed and we are looking for an RVR that reflects this embedding. We show that in this case the problem can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs (i.e., embedded graphs having at most one crossing per edge). The linear time algorithm uses a precise list of forbidden configurations, which extends the set known for straight-line drawings of 1-plane graphs. These forbidden configurations can be tested for in linear time, and so in linear time we can test whether a 1-plane graph has an RVR and either compute such a representation or report a negative witness. Finally, we discuss some extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge.
Recommendations
Cites work
- 1-planarity of graphs with a rotation system
- 1-visibility representations of 1-planar graphs
- A unified approach to visibility representations of planar graphs
- An annotated bibliography on 1-planarity
- Arboricity and Subgraph Listing Algorithms
- Area requirement of visibility representations of trees
- Bar 1-visibility graphs and their relation to other nearly planar graphs
- Bar k-Visibility Graphs
- Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
- Enumeration of simple complete topological graphs
- Fáry's theorem for 1-planar graphs
- Graphs drawn with few crossings per edge
- scientific article; zbMATH DE number 2123123 (Why is no real title available?)
- scientific article; zbMATH DE number 3882450 (Why is no real title available?)
- scientific article; zbMATH DE number 3858396 (Why is no real title available?)
- scientific article; zbMATH DE number 1962799 (Why is no real title available?)
- L-visibility drawings of IC-planar graphs
- Minimal non-1-planar graphs
- Morphing orthogonal planar graph drawings
- Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
- On Diagrams Representing Maps
- On drawings and decompositions of 1-planar graphs
- On Embedding a Graph in the Grid with the Minimum Number of Bends
- On Finding the Rectangular Duals of Planar Triangular Graphs
- On representations of some thickness-two graphs
- On the density of maximal 1-planar graphs
- Re-embeddings of Maximum 1-Planar Graphs
- Recognizing hole-free 4-map graphs in cubic time
- Rectangle and Square Representations of Planar Graphs
- Rectilinear drawings of graphs
- Rectilinear planar layouts and bipolar orientations of planar graphs
- Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
- Relating bends and size in orthogonal graph drawings
- Representing a planar graph by vertical lines joining different levels
- Right angle crossing graphs and 1-planarity
- Straight-line grid drawings of 3-connected 1-planar graphs
- The crossing-angle resolution in graph drawing
- Transversal structures on triangulations: A combinatorial study and straight-line drawings
- Triangulating planar graphs while minimizing the maximum degree
Cited in
(11)- Rectangle-visibility representations of bipartite graphs
- \(\mathsf{T}\)-shape visibility representations of 1-planar graphs
- 1-planarity testing and embedding: an experimental study
- Simultaneous visibility representations of undirected pairs of graphs
- On 3D visibility representations of graphs with few crossings per edge
- On visibility representations of non-planar graphs
- Beyond planar graphs: introduction
- Edge Partitions and Visibility Representations of 1-planar Graphs
- Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
- Rectangular and visibility representations of infinite planar graphs
- Grand-Schnyder woods
This page was built for publication: Embedding-preserving rectangle visibility representations of nonplanar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1991089)
