Outer 1-Planar Graphs
Outer 1-Planar Graphs
复制标题
DOI：
10.1007/s00453-015-0002-1
复制
发表时间：
2016-04
期刊：
影响因子：
1.1
通讯作者：
Christopher Auer;C. Bachmaier;F. Brandenburg;Andreas Gleißner;Kathrin Hanauer;Daniel Neuwirth;Josef Reislhuber
中科院分区：
文献类型：
--
作者：
Christopher Auer;C. Bachmaier;F. Brandenburg;Andreas Gleißner;Kathrin Hanauer;Daniel Neuwirth;Josef Reislhuber
一个图是外1-平面图(O1p)，如果它能在平面内画出所有顶点都在外面且每条边至多相交一次。o1p图是外平面图的推广，它可以在线性时间内被识别，并且是1-平面图的专门化，它的识别是困难的。我们开发了一系列的图片。我们的第一个主要结果是一个线性时间算法，它接受一个图作为输入，并返回1p的一个正或负见证。如果图为1p，则该算法计算嵌入，并且可以扩充为最大图。否则，包括识别算法检测到的六个未成年人中的一个。其次，我们建立了1pgraph的结构性质。o1pgraph是平面图，是具有哈密顿圈的平面图的子图。它们既不在边缘收缩下闭合，也不在细分下闭合。几个重要的图参数，如树宽、可着色性、堆栈数和队列数，比外平面Too1pgraph增加1。每个尺寸图都有最大的边数，并且有最大边数的图数，这些界限是紧的。最后，每个图都有一个所有顶点都在外面的直线网格图，一个平面可见性的区域图，以及一个线性体积的三维直线图，这些图都可以在线性时间内构造。
A graph is outer 1-planar (o1p) if it can be drawn in the plane such that all vertices are in the outer face and each edge is crossed at most once.o1pgraphs generalize outerplanar graphs, which can be recognized in linear time, and specialize 1-planar graphs, whose recognition is-hard. We exploreo1pgraphs. Our first main result is a linear-time algorithm that takes a graph as input and returns a positive or a negative witness foro1p. If a graphiso1p, then the algorithm computes an embedding and can augmentto a maximalo1pgraph. Otherwise,includes one of six minors, which is detected by the recognition algorithm. Secondly, we establish structural properties ofo1pgraphs.o1pgraphs are planar and are subgraphs of planar graphs with a Hamiltonian cycle. They are neither closed under edge contraction nor under subdivision. Several important graph parameters, such as treewidth, colorability, stack number, and queue number, increase by one from outerplanar too1pgraphs. Everyo1pgraph of sizehas at mostedges and there are maximalo1pgraphs withedges, and these bounds are tight. Finally, everyo1pgraph has a straight-line grid drawing inarea with all vertices in the outer face, a planar visibility representation inarea, and a 3D straight-line drawing in linear volume, and these drawings can be constructed in linear time.