1. Ortho-polygon Visibility Representations of Embedded Graphs.
- Author
-
Di Giacomo, Emilio, Didimo, Walter, Evans, William S., Liotta, Giuseppe, Meijer, Henk, Montecchiani, Fabrizio, and Wismath, Stephen K.
- Subjects
- *
GRAPH theory , *REPRESENTATIONS of graphs , *EMBEDDINGS (Mathematics) , *PATHS & cycles in graph theory , *POLYNOMIAL time algorithms - Abstract
An ortho-polygon visibility representation of an
n -vertex embedded graphG (OPVR ofG ) is an embedding-preserving drawing ofG that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR ofG is the minimumk such that every polygon has at mostk reflex corners. We present polynomial time algorithms that test whetherG has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR ofG are related to its number of crossings per edge and to its connectivity. More precisely, we prove that ifG has at most one crossing per edge (i.e.,G is a 1-plane graph), an OPVR ofG always exists while this may not be the case if two crossings per edge are allowed. Also, ifG is a 3-connected 1-plane graph, we can compute an OPVR ofG whose vertex complexity is bounded by a constant inO (n ) time. However, ifG is a 2-connected 1-plane graph, the vertex complexity of any OPVR ofG may be Ω(n). In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O (n ) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs. [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF