An Exponential Bound for Simultaneous Embeddings of Planar Graphs

被引：0
作者：
Ritesh Goenka
Pardis Semnani
Chi Hoi Yip
机构：
[1] University of British Columbia,Department of Mathematics
来源：
Graphs and Combinatorics | 2023年 / 39卷
关键词：
Graph drawing; Planar graphs; Simultaneous straight-line embeddings; 05C62; 68R10; 05C10;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We show that there are O(n·4n/11)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n \cdot 4^{n/11})$$\end{document} planar graphs on n vertices which do not admit a simultaneous straight-line embedding on any n-point set in the plane. In particular, this improves the best known bound O(n!) significantly.
引用
收藏
相关论文
共 29 条
[1]  
Bannister MJ(2014)Superpatterns and universal point sets J. Graph Algorithms Appl. 18 177-209
[2]  
Cheng Z(2007)On simultaneous planar graph embeddings Comput. Geom. 36 117-130
[3]  
Devanny WE(2015)On universal point sets for planar graphs J. Graph Algorithms Appl. 19 529-547
[4]  
Eppstein D(1989)A lower bound on the size of universal sets for planar graphs ACM SIGACT News 20 83-86
[5]  
Brass P(1995)A linear-time algorithm for drawing a planar graph on a grid Inform. Process. Lett. 54 241-246
[6]  
Cenek E(1948)On straight-line representing of planar graphs Acta Sci. Math. (Szeged) 11 229-233
[7]  
Duncan CA(1990)How to draw a planar graph on a grid Combinatorica 10 41-51
[8]  
Efrat A(2004)A Inform. Process. Lett. 92 95-98
[9]  
Erten C(2020) lower bound on the number of points needed to draw all J. Graph Algorithms Appl. 24 247-267
[10]  
Ismailescu DP(1936)-vertex planar graphs Jahresbericht Deutsch. Math. Verein. 46 26-32
123