Ortho-Polygon Visibility Representations of Embedded Graphs

Di Giacomo, Emilio and Didimo, Walter and Evans, William S. and Liotta, Giuseppe and Meijer, Henk and Montecchiani, Fabrizio and Wismath, Stephen (2016) Ortho-Polygon Visibility Representations of Embedded Graphs. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 280-294(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_22).

Full text not available from this repository.


An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding preserving drawing of G 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 of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. Namely, we prove that if G is 1-plane (i.e., it has at most one crossing per edge) an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute in O(n) time an OPVR of G whose vertex complexity is bounded by a constant. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G 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. Finally, we present the results of an experimental study on the vertex complexity of OPVRs of 1-plane graphs.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.560 Geometry
P Styles > P.900 Visibility
P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1549

Actions (login required)

View Item View Item