In a representation of a graph $G$ as an edge intersection graph of paths on a grid (EPG) every vertex of $G$ is represented by a path on a grid and two paths share a grid edge iff the corresponding vertices are adjacent. In a monotonic EPG representation every path on the grid is ascending in both rows and columns. In a (monotonic) $B_k$-EPG representation every path on the grid has at most $k$ bends. The (monotonic) bend number $b(G)$ ($b^m(G)$) of a graph $G$ is the smallest natural number $k$ for which there exists a (monotonic) $B_k$-EPG representation of $G$. In this paper we deal with the monotonic bend number of outerplanar graphs and show that $b^m(G)\leqslant 2$ holds for every outerplanar graph $G$. Moreover, we characterize the maximal outerplanar graphs and the cacti with (monotonic) bend number equal to $0$, $1$ and $2$ in terms of forbidden induced subgraphs. As a byproduct we obtain low-degree polynomial time algorithms to construct (monotonic) EPG representations with the smallest possible number of bends for maximal outerplanar graphs and cacti.


翻译:以图形 $G$ 表示在网格( EPG) 上路径的边缘交叉图示中, 每一个顶点 $G$ 以网格上的一条路径代表$G$, 如果相应的顶点是相邻的, 两条路径以网格上的一条网点边缘为代表一个网格。 在单调 EPG 中, 网格上的每一条路径都在上升。 在( monocontic) $B_ k$- EPG 中, 每条网格( monocicial) 代表着每个外平面图的弯曲点最多为$k美元。 此外, 图表( mononocicial) 的弯曲号是最小的自然数 $GG$ 。 在本文中, 我们处理外平面图的单调弯曲号数为$B$G$G$G$, 显示每个外平面图的弯曲号为$G$。 此外, 我们用最大外平面图和cactical$ 最小平面图( monocial$) 代表一个硬度的硬度数字, 等为美元。

0
下载
关闭预览

相关内容

Into the Metaverse,93页ppt介绍元宇宙概念、应用、趋势
专知会员服务
47+阅读 · 2022年2月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
中国图象图形学学会CSIG
0+阅读 · 2021年11月15日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
中国图象图形学学会CSIG
1+阅读 · 2021年11月11日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年10月20日
Arxiv
0+阅读 · 2022年10月17日
Directional Graph Networks
Arxiv
27+阅读 · 2020年12月10日
Arxiv
38+阅读 · 2020年3月10日
VIP会员
相关资讯
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
中国图象图形学学会CSIG
0+阅读 · 2021年11月15日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
中国图象图形学学会CSIG
1+阅读 · 2021年11月11日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
相关论文
相关基金
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员