Search engine for discovering works of Art, research articles, and books related to Art and Culture
ShareThis
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 .
Springer Science and Business Media LLC
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...
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...

Back to Top