Embedding-Preserving Rectangle Visibility Representations of Nonplanar Graphs
| Autor: | Fabrizio Montecchiani, Therese C. Biedl, Giuseppe Liotta |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Visibility representations
1-Planarity Fixed embedding Forbidden configuration Theoretical Computer Science Geometry and Topology Discrete Mathematics and Combinatorics Computational Theory and Mathematics Existential quantification 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 0202 electrical engineering electronic engineering information engineering Embedding 020201 artificial intelligence & image processing Rectangle Time complexity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete & Computational Geometry. 60:345-380 |
| ISSN: | 1432-0444 0179-5376 |
| DOI: | 10.1007/s00454-017-9939-y |
| Popis: | A (weak) rectangle visibility representation, or simply an 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. Given a graph with a fixed embedding in the plane, we show that the problem of testing whether this graph has an embedding-preserving RVR can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs, i.e., for embedded graphs having at most one crossing per edge. The linear time algorithm uses three forbidden configurations, which extend the set known for straight-line drawings of 1-plane graphs. The algorithm first checks for the presence of these forbidden configurations in the input graph, and then either an embedding-preserving RVR is computed (also in linear time) or a forbidden configuration is reported as a negative witness. Finally, we discuss extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink