1. HV-planarity: Algorithms and complexity
- Author
-
Maurizio Patrignani, Walter Didimo, Giuseppe Liotta, Didimo, Walter, Liotta, Giuseppe, and Patrignani, Maurizio
- Subjects
General Computer Science ,Computer Networks and Communications ,Graph Drawing ,Orthogonal drawings ,0102 computer and information sciences ,02 engineering and technology ,Computer Science::Computational Geometry ,Edge (geometry) ,Orthogonal drawing ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,symbols.namesake ,Planar ,Graph drawing ,Computational Theory and Mathematic ,020204 information systems ,Testing algorithms ,0202 electrical engineering, electronic engineering, information engineering ,Complexity ,HV-planarity ,Computational Theory and Mathematics ,Applied Mathematics ,Mathematics ,Testing algorithm ,Planarity testing ,Planar graph ,Computer Networks and Communication ,010201 computation theory & mathematics ,symbols ,Vertical segment - Abstract
An HV-graph is a planar graph with vertex-degree at most four such that each edge is labeled either H (horizontal) or V (vertical). The HV-planarity testing problem asks whether an HV-graph admits an HV-drawing, that is, a planar drawing such that each edge with label H is drawn as a horizontal segment and each edge with label V is drawn as a vertical segment. We prove that the HV-planarity testing problem is NP-complete even for graphs with vertex-degree at most three, which answers an open question posed by both Manuch et al. [30] and Durocher et al. [17] . On the positive side, we prove that the HV-planarity testing problem can be solved in polynomial-time for series-parallel graphs. This result significantly extends a previous result by Durocher et al. about HV-planarity testing of biconnected outerplanar graphs of maximum vertex-degree three.
- Published
- 2019