On the Complexity of HVrectilinear Planarity TestingDidimo, Walter and Liotta, Giuseppe and Patrignani, Maurizio (2014) On the Complexity of HVrectilinear Planarity Testing. In: Graph Drawing 22nd International Symposium, GD 2014, September 2426, 2014 , pp. 343354(Official URL: http://dx.doi.org/10.1007/9783662458037_29). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783662458037_29
AbstractAn HVrestricted planar graph G is a planar graph with vertexdegree at most four and such that each edge is labeled either H (horizontal) or V (vertical). The HVrectilinear planarity testing problem asks whether G admits a planar drawing where every edge labeled V is drawn as a vertical segment and every edge labeled H is drawn as a horizontal segment. We prove that HVrectilinear planarity testing is NPcomplete even for graphs having vertex degree at most three, which solves an open problem posed by both Manuch et al. (GD 2010) and Durucher et al. (LATIN 2014). We also show that HVrectilinear planarity can be tested in polynomial time for partial 2trees of maximum degree four, which extends a previous result by Durucher et al. (LATIN 2014) about HVrestricted planarity testing of biconnected outerplanar graphs of maximum degree three. When the test is positive, our algorithm returns an orthogonal representation of G that satisfies the given H and Vlabels on the edges.
Actions (login required)
