弦二分图的矩形镶嵌
《Theoretical Computer Science》:Rectilinear embeddings of chordal bipartite graphs
【字体:
大
中
小
】
时间:2026年08月29日
来源:Theoretical Computer Science 1.1
编辑推荐:
# 弦双分图的正交直线嵌入
## 摘要
在本工作中,我们研究了寻找最大度为4的弦双分图的直线嵌入问题,即所谓的s-模型。针对此类图,我们提出了一个时间复杂度为O(n2)的算法,用于在存在时找到图G的s-模型,或在不存在时给出G无法进行正交嵌入的反证证书。我们利用BC树和褪
# 弦双分图的正交直线嵌入
## 摘要
在本工作中,我们研究了寻找最大度为4的弦双分图的直线嵌入问题,即所谓的s-模型。针对此类图,我们提出了一个时间复杂度为O(n2)的算法,用于在存在时找到图G的s-模型,或在不存在时给出G无法进行正交嵌入的反证证书。我们利用BC树和褪色表示的概念作为构建此类图s模型的关键工具。该问题已被证明对于边必须具有单位长度的双连通图而言是NP难问题。
## 引言
给定一个图G,将G嵌入到平面上意味着将G的每个顶点对应到平面上的一个点,将G的每条边uv对应到连接u和v所对应点的(可能弯曲的)线段。当没有两条线段相互交叉(端点除外)时,该嵌入被称为平面嵌入。图1(a)展示了K4的一个嵌入示例,图1(b)展示了同一图的一个平面嵌入示例。G的直线嵌入是指G的平面嵌入,其中所有线段都是直线。图1(c)展示了K4的一个直线嵌入示例。寻找图的直线嵌入问题在图论中有着悠久的历史[1]。Fáry[1]的一个经典结果指出,每个平面图都有一个直线嵌入。
图中每条线段由若干水平和垂直线段组成的平面嵌入称为正交嵌入。寻找正交嵌入的问题等价于网格嵌入问题,该问题要求将图G嵌入到一个矩形二维网格(简称为网格)中,使得G的每个顶点v对应于一个网格点(水平网格线与垂直网格线的交点),G的每条边uv对应于连接u和v所对应网格点之间的内部不相交路径,路径沿网格线行进。如果一个网格嵌入使用了r条水平网格线和s条垂直网格线,我们说它嵌入在r×s网格中。图1(d)展示了K4的一个正交(或4×5网格)嵌入示例(在图中,我们通常省略网格,仅展示正交嵌入)。注意,边bd由三段线段表示(其中两段为垂直段,一段为水平段)。每条线中水平/垂直线段相交的点称为弯折,由给定路径的方向变化所定义。
图的网格嵌入已从不同角度进行了研究[2]、[3]、[4]、[5]、[6]、[7]、[8]。在[2]中,作者描述了一个嵌入平面图的算法,并证明所得嵌入的边最多有6个弯折。同一作者后来在[3]中展示了一种更简单的方法,得到的嵌入中每条边最多有4个弯折。边最多有4个弯折的嵌入也在[8]中被考虑,其中提出了一个线性时间算法。在[5]中,描述了线性时间算法用于嵌入平面图,使得所得嵌入保证每条边最多有2个弯折,八面体除外,对于八面体可能产生最多两条具有3个弯折的边。在同一篇论文中,作者还提供了其嵌入中弯折总数的上界。
直线嵌入是指直线正交嵌入,即每条曲线段要么是水平线段要么是垂直线段的平面嵌入。如果一个图允许直线嵌入,则该图称为正交可嵌入的。并非所有平面图都是正交可嵌入的。例如,C?不允许直线嵌入。因此,图1中以不同嵌入方式表示的图不允许直线嵌入。图1(e)展示了C?的一个直线嵌入。
在[9]中,提出了一种二次时间算法用于确定最小化所有叶到叶路径上弯折数的树的直线嵌入,该算法在[6]中被改进为线性时间算法。
构建弯折数最少的正交图嵌入问题已被研究了数十年。1987年,Tamassia[10]证明了对于一个具有预定平面嵌入的平面图,可以在多项式时间内构造出满足预定平面嵌入且弯折数最少的正交嵌入,这回答了Storer[11]提出的问题,并奠定了图绘制研究的基础。Tamassia算法的运行时间为O(n2log n)(n为顶点数)。Garg和Tamassia[12]将其改进为O(n^(7/4)√log n),随后Cornelsen和Karrenbauer[13]将其改进为O(n^(3/2))。
可变嵌入设置下的弯折最小化问题更为困难;Garg和Tamassia[14]证明了测试一个图是否存在直线嵌入是NP难的。尽管如此,某些自然的限制条件使该问题变得可处理。例如,Di Battista等人[15]表明,对于最大度为3的平面图,可以在O(n?log n)时间内构造弯折数最少的正交嵌入。经过进一步改进[16]、[17],Didimo等人[18]最近实现了线性时间解决方案。Di Battista等人[15]还提出了一种O(n?)时间算法用于最小化2-连通串联并行图正交嵌入中的弯折数,Bl?sius等人[19]后来将其扩展到不一定是2-连通的串联并行图,Di Giacomo等人[20]将其改进为O(n3log n)。
证据表明,当聚焦于直线嵌入时,弯折最小化问题几乎一样困难。Garg和Tamassia[14]的NP难证明适用于平面直线嵌入。此外,大多数测试直线嵌入的高效算法都被更一般的弯折最小化问题的算法所包含。这对于可变嵌入的最大度为3的串联并行图(见[21]和[22])、固定嵌入的最大度为3的平面图(见[23]和[24])、以及可变嵌入的最大度为3的平面图(见[18]和[25])均适用。然而,对于具有固定嵌入的平面图,目前最快的弯折最小化算法运行时间为O(n^(3/2))(Cornelsen和Karrenbauer[13]),而最快的直线嵌入测试算法运行时间为O(nlog3n),可以通过Borradaile等人[26]在Tamassia的弯折最小化问题流网络表述[10]中的最新结果实现。
显然,平面图具有直线嵌入的一个必要条件是该图不含C?且最大度为4。Alegria等人[27]建立了判断单位矩形绘制(内部面为矩形且边具有单位长度的直线嵌入)存在的问题的复杂度二分性,取决于是否要求外部面绘制为矩形。具体而言,作者证明当不要求外部面为矩形时,该问题对于双连通图是NP完全的,即使组合嵌入是固定的;而当要求外部面为矩形时,无论是在固定嵌入还是可变嵌入设置下,该问题都可以在多项式时间内求解。他们还建立了一种O(n2log3n)时间算法用于测试最大度为4的平面图在外部面被指定时是否存在(不一定是单位的)矩形绘制。我们的论文直接建立在这些结果之上:我们提供了一种O(n2)时间算法,输入为最大度为4且对所有k≥5满足不含C?的图G,如果存在则返回G的直线嵌入。对外部面不施加任何约束,这恰好落在[27]中确定的NP难范围内。诱导圈仅为C?的图称为弦双分图。
## 预备知识
在本文中,所有考虑的图都是无向的、有限的和简单的。设G为一个图。我们用V(G)表示G的顶点集,用E(G)表示G的边集,记为G=(V(G), E(G))。如果上下文中有一个明确的图,则n和m分别表示|V(G)|和|E(G)|,除非另有说明。v∈V(G)的邻域定义为N_G(v)={u∈V(G)|vu∈E(G)}。v在G中的度定义为d_G(v)=|N_G(v)|,Δ(G)表示G中所有顶点的最大度。
## 弦双分图的直线嵌入
回顾一下,Δ(G)≤4是图G允许直线嵌入的一个必要条件。设G为一个Δ(G)≤4的弦双分图。考虑寻找G的直线嵌入的问题(如果存在),我们称之为G的直线模型,简称G的s-模型,沿用[6]中的术语。
设?为图G的一个s-模型,v∈V(G)。假设N_G(v)={u?|1≤i≤d(v)},即v的邻居为u?,…,u_d(v)。对于后续内容,为方便起见将……
## 结论
在本工作中,我们研究了寻找最大度为4的弦双分图的直线嵌入问题,即s-模型。针对此类图,我们提出了一种O(n2)时间算法,用于在存在时找到图G的s-模型,或在不存在时给出反证证书。我们利用BC树和褪色表示的概念作为构建此类图s模型的关键工具。作为未来工作,研究寻找图的直线嵌入的算法将很有趣。
## CRediT作者贡献声明
Vitor Tocci Ferreira de Luca:撰写——审阅与编辑,撰写——原始草稿,构思。
María Pía Mazzoleni:撰写——审阅与编辑,监督,构思。
Fabiano de Souza Oliveira:撰写——审阅与编辑,监督,构思。
Jayme Luiz Szwarcfiter:撰写——审阅与编辑,监督,构思。
## 利益冲突声明
作者声明他们没有已知的 competing financial interests 或个人关系可能影响本文报告的工作。
Vitor Tocci Ferreira de Luca | María Pía Mazzoleni | Fabiano de Souza Oliveira | Jayme Luiz Szwarcfiter
里约热内卢联邦大学,里约热内卢,里约热内卢,巴西
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号