Javascript must be enabled to continue!
Rooted Bicubic Planar Maps via Dyck Paths
View through CrossRef
Abstract
We provide a combinatorial proof of Tutte’s decomposition of rooted bicubic planar maps into 3-connected components. Motivated by the framework of Bell transformations, we establish an explicit bijection between rooted bicubic planar maps on 2
n
vertices and Dyck paths of semilength 3
n
with ascents of length divisible by 3, where each 3
j
-ascent is colored using one of
$$g_j$$
g
j
colors corresponding to the rooted 3-connected bicubic maps on 2
j
vertices. Our bijection gives a constructive method for assembling all rooted bicubic planar maps from their 3-connected building blocks. We give a simple proof for the fact that every 3-connected bicubic planar map on 2
n
vertices with
$$n \ge 4$$
n
≥
4
can be obtained from a smaller primitive map through just two insertion operations that add either 4 or 6 vertices. Finally, we briefly discuss rootings of 3-connected bicubic maps, providing lower bounds on the minimal number of rootings and showing that prism graphs can be used in combination with our insertion operations to generate maps with the maximum of 6
n
distinct rootings for all
$$n \ge 11$$
n
≥
11
.
Title: Rooted Bicubic Planar Maps via Dyck Paths
Description:
Abstract
We provide a combinatorial proof of Tutte’s decomposition of rooted bicubic planar maps into 3-connected components.
Motivated by the framework of Bell transformations, we establish an explicit bijection between rooted bicubic planar maps on 2
n
vertices and Dyck paths of semilength 3
n
with ascents of length divisible by 3, where each 3
j
-ascent is colored using one of
$$g_j$$
g
j
colors corresponding to the rooted 3-connected bicubic maps on 2
j
vertices.
Our bijection gives a constructive method for assembling all rooted bicubic planar maps from their 3-connected building blocks.
We give a simple proof for the fact that every 3-connected bicubic planar map on 2
n
vertices with
$$n \ge 4$$
n
≥
4
can be obtained from a smaller primitive map through just two insertion operations that add either 4 or 6 vertices.
Finally, we briefly discuss rootings of 3-connected bicubic maps, providing lower bounds on the minimal number of rootings and showing that prism graphs can be used in combination with our insertion operations to generate maps with the maximum of 6
n
distinct rootings for all
$$n \ge 11$$
n
≥
11
.
Related Results
Engineering Design Methodology for Robot-Based Non-Planar Additive Manufacturing (RbNPAM)
Engineering Design Methodology for Robot-Based Non-Planar Additive Manufacturing (RbNPAM)
Robot-Based Non-Planar Additive Manufacturing (RbNPAM) explores advancements in integrating robotics with additive manufacturing, focusing on the development and application of non...
Row-column combination of Dyck words
Row-column combination of Dyck words
Abstract
We extend the notion of the Dyck language from words to two-dimensional arrays of symbols, i.e., pictures, using the row-column combination (also known as the cr...
Απαρίθμηση προτύπων σε μονοπάτια Dyck και Grand-Dyck
Απαρίθμηση προτύπων σε μονοπάτια Dyck και Grand-Dyck
Οι αριθμοί Catalan θεωρούνται ως οι πιο σημαντικοί αριθμοί της Συνδυαστικής, μετά τους διωνυμικούς συντελεστές, λόγω της εντυπωσιακά συχνής εμφάνισής τους σε διάφορα προβλήματα. Εν...
Analisa Perbandingan GPS Google Maps Dan GPS Google Earth Dalam Penentuan Titik Koordinat Breeding Place
Analisa Perbandingan GPS Google Maps Dan GPS Google Earth Dalam Penentuan Titik Koordinat Breeding Place
INTISARINyamuk Aedes Aegypti menularkan penyakit DBD (Demam Berdarah Dengue) ke manusia dengan gigitannya. Breeding Place merupakan berkembangbiaknya jentik nyamuk di tempat pe...
A Graph Based Design Methodology for Compliant Mechanisms (Non Linear Springs) to More Fully Explore and Exploit the Design Domain
A Graph Based Design Methodology for Compliant Mechanisms (Non Linear Springs) to More Fully Explore and Exploit the Design Domain
Abstract
Nonlinear springs are compliant mechanisms that may provide desired force versus displacement relations that give rise to improved energy storage, and impro...
The Effects of Map Reading Expertise and Map Type on Eye Movements in Map Comparison Tasks
The Effects of Map Reading Expertise and Map Type on Eye Movements in Map Comparison Tasks
Comparing maps of different geographical phenomena, or maps of the same geographical phenomenon at different points in time, is a frequent task in many disciplines. The process of ...
The Effects of Map Reading Expertise and Map Type on Eye Movements in Map Comparison Tasks
The Effects of Map Reading Expertise and Map Type on Eye Movements in Map Comparison Tasks
Comparing maps of different geographical phenomena, or maps of the same geographical phenomenon at different points in time, is a frequent task in many disciplines. The process of ...
The Cognitive Life of Maps
The Cognitive Life of Maps
The “mapness of maps”—how maps live in interaction with their users, and what this tells us about what they are and how they work.
In a sense, maps are temporarily a...

