Ortho-polygon Visibility Representations of 3-connected 1-plane Graphs
| Autor: | Alessandra Tappini, Fabrizio Montecchiani, Giuseppe Liotta |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Visibility representations
Computational Geometry (cs.CG) FOS: Computer and information sciences Vertex (graph theory) General Computer Science Theoretical Computer Science Computer Science (all) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Upper and lower bounds Combinatorics Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) 0101 mathematics 1-plane graphs Mathematics 010102 general mathematics Graph 010201 computation theory & mathematics Embedding Computer Science - Computational Geometry 020201 artificial intelligence & image processing Vertex complexity Integer grid |
| Zdroj: | Graph Drawing Lecture Notes in Computer Science ISBN: 9783030044138 |
| Popis: | An ortho-polygon visibility representation $\Gamma$ of a $1$-plane graph $G$ (OPVR of $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. The representation $\Gamma$ has vertex complexity $k$ if every polygon of $\Gamma$ has at most $k$ reflex corners. It is known that $3$-connected $1$-plane graphs admit an OPVR with vertex complexity at most twelve, while vertex complexity at least two may be required in some cases. In this paper, we reduce this gap by showing that vertex complexity five is always sufficient, while vertex complexity four may be required in some cases. 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 $\tilde{O}(n^\frac{10}{7})$-time drawing algorithm that computes an OPVR of an $n$-vertex $3$-connected $1$-plane graph on an integer grid of size $O(n) \times O(n)$ and with vertex complexity at most five. Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|