HV-planarity: Algorithms and complexity

作者：

Highlights：

• HV-planarity testing is NP-complete, even for graphs with vertex-degree at most 3.

• Polynomial-time HV-planarity testing for 2-connected series-parallel graphs.

• Polynomial-time HV-planarity testing for partial 2-trees.

摘要

•HV-planarity testing is NP-complete, even for graphs with vertex-degree at most 3.•Polynomial-time HV-planarity testing for 2-connected series-parallel graphs.•Polynomial-time HV-planarity testing for partial 2-trees.

论文关键词：Graph Drawing,Orthogonal drawings,HV-planarity,Testing algorithms,Complexity

论文评审过程：Received 2 October 2015, Revised 1 October 2017, Accepted 8 August 2018, Available online 21 September 2018, Version of Record 10 October 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.08.003