Monotone Drawings of 3-Connected Plane Graphs
Monotone Drawings of 3-Connected Plane Graphs
复制标题
3 连通平面图的单调绘图
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Dayu He
中科院分区：
文献类型：
--
作者：
Xin He;Dayu He
图G的单调图是G的直线图，使得对于G中的每一对顶点u，w，存在G中的路Puw，该路在某条直线luw上是单调的。（也就是说，P uw中的顶点在l uw上的正交投影的顺序与它们在P uw中出现的顺序相同。本文证明了3连通平面图的经典Schnyder图是在大小为f ×f（f ≤ 2n − 5是G的内面数）的网格上的单调图，它可以在O（n）时间内构造。它还有一个优点，对于任何给定的顶点u，w，单调线l uw可以在O（1）时间内确定。
A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists a path P uw in G that is monotone on some line l uw . (Namely, the order of the orthogonal projections of the vertices in P uw on l uw is the same as the order they appear in P uw .) In this paper, we show that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a grid of size f ×f (f ≤ 2n − 5 is the number of internal faces of G), which can be constructed in O(n) time. It also has the advantage that, for any given vertices u,w, the monotone line l uw can be identified in O(1) time.