Three-dimensional grid drawings with sub-quadratic volume

被引：0
|
作者：
Dujmovic, V [1 ]
Wood, DR
机构：
[1] McGill Univ, Sch Comp Sci, Montreal, PQ, Canada
[2] Carleton Univ, Sch Comp Sci, Ottawa, ON K1S 5B6, Canada
来源：
GRAPH DRAWING | 2004年 / 2912卷
关键词：
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise non-crossing. A O(n(3/2)) volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was O(n(2)). These results (partially) solve open problems due to Pach, Thiele, and Toth [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001].
引用
收藏
页码：190 / 201
页数：12
相关论文
共 50 条
  • [31] ON FRACTIONAL HAMILTONIAN SYSTEMS WITH INDEFINITE SIGN SUB-QUADRATIC POTENTIALS
    Chen, Peng
    Li, Meng
    Zhang, Yuanyuan
    DIFFERENTIAL AND INTEGRAL EQUATIONS, 2021, 34 (3-4) : 165 - 182
  • [32] A simple sub-quadratic algorithm for computing the subset partial order
    Pritchard, P
    INFORMATION PROCESSING LETTERS, 1995, 56 (06) : 337 - 341
  • [33] Learning directed acyclic graph SPNs in sub-quadratic time
    Ghose, Amur
    Jaini, Priyank
    Poupart, Pascal
    INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, 2020, 120 : 48 - 73
  • [34] Interaction Hard Thresholding: Consistent Sparse Quadratic Regression in Sub-quadratic Time and Space
    Yang, Shuo
    Shen, Yanyao
    Sanghavi, Sujay
    ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019), 2019, 32
  • [35] Numerical method of compressible flow on three-dimensional sub-block unstructured grid
    School of Energy and Power Engineering, Xi'an Jiaotong University, Xi'an 710049, China
    Hangkong Dongli Xuebao, 2009, 10 (2319-2325):
  • [36] Three-Dimensional Quadratic Nonconforming Brick Element
    Meng, Zhaoliang
    Sheen, Dongwoo
    Luo, Zhongxuan
    Kim, Sihwan
    NUMERICAL METHODS FOR PARTIAL DIFFERENTIAL EQUATIONS, 2014, 30 (01) : 158 - 174
  • [37] Pathways to hyperchaos in a three-dimensional quadratic map
    Muni, Sishu Shankar
    EUROPEAN PHYSICAL JOURNAL PLUS, 2024, 139 (07):
  • [38] On the Integrability of Persistent Quadratic Three-Dimensional Systems
    Fercec, Brigita
    Zulj, Maja
    Mencinger, Matej
    MATHEMATICS, 2024, 12 (09)
  • [39] SINGULAR LIMITS FOR 2-DIMENSIONAL ELLIPTIC PROBLEMS INVOLVING EXPONENTIAL NONLINEARITIES WITH SUB-QUADRATIC CONVECTION TERM
    Baraket, Sami
    Ouni, Taieb
    GLASGOW MATHEMATICAL JOURNAL, 2013, 55 (03) : 537 - 557
  • [40] Quadratic algebras for three-dimensional superintegrable systems
    C. Daskaloyannis
    Y. Tanoudis
    Physics of Atomic Nuclei, 2010, 73 : 214 - 221
12345