Monotone drawings of graphs with few directions

详细信息    查看全文

• 作者：Patrizio Angelini p>angelini@informatik.uni-tuebingen.dep>
• 关键词：Monotone drawings ; Schnyder woods ; Graph algorithms ; Maximal planar graphs ; Hamiltonian graphs
• 刊名：Information Processing Letters
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：120
• 期：Complete
• 页码：16-22
• 全文大小：370 K
• 卷排序：120

文摘

We define k-monotone drawings, where paths are monotone in one of k directions. We prove that a graph admits a 1-monotone drawing if and only if it can be made Hamiltonian by adding at most one edge. We prove that maximal planar graphs admit 2-monotone drawings. We prove that triconnected planar graphs admit 3-monotone drawings.