Distance matching in punctured planar triangulations

被引:5
作者
Aldred, R. E. L. [1 ]
Plummer, Michael D. [2 ]
机构
[1] Univ Otago, Dept Math & Stat, POB 56, Dunedin 9054, New Zealand
[2] Vanderbilt Univ, Dept Math, Nashville, TN 37240 USA
关键词
D O I
10.4310/JOC.2016.v7.n2.a15
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Distance matching extension with prescribed and proscribed edges in planar triangulations has been previously studied. In the present work, matching extension behavior is investigated when the graph families are slightly more general than triangulations. More particularly, we replace the triangulation hypothesis with the weaker hypotheses that (a) the graph is locally connected and (b) the graph has at most two non-triangular faces. We investigate which distance matching properties enjoyed by triangulations are retained and which are lost.
引用
收藏
页码:509 / 530
页数:22
相关论文
共 50 条
[31]   On random planar graphs, the number of planar graphs and their triangulations [J].
Osthus, D ;
Prömel, HJ ;
Taraz, A .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 88 (01) :119-134
[32]   A GENERATING THEOREM OF PUNCTURED SURFACE TRIANGULATIONS WITH INNER DEGREE AT LEAST 4 [J].
Chavez, Maria-Jose ;
Negami, Seiya ;
Quintero, Antonio ;
Villar-Linan, Maria Trinidad .
MATHEMATICA SLOVACA, 2019, 69 (05) :969-978
[33]   Controllable morphing of compatible planar triangulations [J].
Surazhsky, V ;
Gotsman, C .
ACM TRANSACTIONS ON GRAPHICS, 2001, 20 (04) :203-231
[34]   Counting Triangulations of Planar Point Sets [J].
Sharir, Micha ;
Sheffer, Adam .
ELECTRONIC JOURNAL OF COMBINATORICS, 2011, 18 (01)
[35]   On the number of triangulations of planar point sets [J].
Seidel, R .
COMBINATORICA, 1998, 18 (02) :297-299
[36]   Geometry and percolation on half planar triangulations [J].
Ray, Gourab .
ELECTRONIC JOURNAL OF PROBABILITY, 2014, 19 :1-28
[37]   Morphing Schnyder Drawings of Planar Triangulations [J].
Fidel Barrera-Cruz ;
Penny Haxell ;
Anna Lubiw .
Discrete & Computational Geometry, 2019, 61 :161-184
[38]   Contracting planar graphs to contractions of triangulations [J].
Kaminski, Marcin ;
Paulusma, Daniel ;
Thilikos, Dimitrios M. .
JOURNAL OF DISCRETE ALGORITHMS, 2011, 9 (03) :299-306
[39]   Morphing Schnyder Drawings of Planar Triangulations [J].
Barrera-Cruz, Fidel ;
Haxell, Penny ;
Lubiw, Anna .
DISCRETE & COMPUTATIONAL GEOMETRY, 2019, 61 (01) :161-184
[40]   Bounds for the Oriented Diameter of Planar Triangulations [J].
Mondal, Debajyoti ;
Parthiban, N. ;
Rajasingh, Indra .
FRONTIERS OF ALGORITHMIC WISDOM, IJTCS-FAW 2022, 2022, 13461 :192-205