On the Complexity of HV-rectilinear Planarity Testing

Didimo, Walter and Liotta, Giuseppe and Patrignani, Maurizio (2014) On the Complexity of HV-rectilinear Planarity Testing. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 343-354(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_29).

Full text not available from this repository.

Abstract

An HV-restricted planar graph G is a planar graph with vertex-degree at most four and such that each edge is labeled either H (horizontal) or V (vertical). The HV-rectilinear 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 HV-rectilinear planarity testing is NP-complete 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 HV-rectilinear planarity can be tested in polynomial time for partial 2-trees of maximum degree four, which extends a previous result by Durucher et al. (LATIN 2014) about HV-restricted 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 V-labels on the edges.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-662-45803-7_29
Classifications:	G Algorithms and Complexity > G.630 Labeling G Algorithms and Complexity > G.770 Planarity Testing M Methods > M.900 Tree P Styles > P.600 Poly-line > P.600.700 Orthogonal Z Theory > Z.750 Topology
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1445

Actions (login required)

View Item