OrthoPolygon Visibility Representations of Embedded GraphsDi Giacomo, Emilio and Didimo, Walter and Evans, William S. and Liotta, Giuseppe and Meijer, Henk and Montecchiani, Fabrizio and Wismath, Stephen (2016) OrthoPolygon Visibility Representations of Embedded Graphs. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 280294(Official URL: http://dx.doi.org/10.1007/9783319501062_22). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_22
AbstractAn orthopolygon visibility representation of an nvertex 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 endvertices. 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 1plane (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 3connected 1plane 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 2connected 1plane graph, the vertex complexity of any OPVR of G may be Ω(n). In contrast, we describe a family of 2connected 1plane 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 1plane graphs.
Actions (login required)
