View source for Regular map (graph theory)

{{short description|Symmetric tessellation of a closed surface}}
{{See also|Regular map (algebraic geometry)}}

[[File:Hexagonal Hosohedron.svg|thumb|The hexagonal [[hosohedron]], a regular map on the sphere with two vertices, six edges, six faces, and 24 flags.]]
[[File:Regmap-6340.png|thumb|The regular map {6,3}<sub>''4'',''0''</sub> on the torus with 16 faces, 32 vertices and 48 edges.]]

In [[mathematics]], a '''regular map''' is a symmetric [[tessellation]] of a closed [[surface (topology)|surface]]. More precisely, a regular map is a [[Manifold decomposition|decomposition]] of a two-dimensional [[manifold]] (such as a [[sphere]], [[torus]], or [[real projective plane]]) into topological disks such that every [[Flag (geometry)|flag]] (an incident vertex-edge-face triple) can be transformed into any other flag by a [[automorphism group|symmetry]] of the decomposition. Regular maps are, in a sense, topological generalizations of [[Platonic solid]]s.  The theory of maps and their classification is related to the theory of [[Riemann surface]]s, [[hyperbolic geometry]], and [[Galois theory]]. Regular maps are classified according to either: the [[genus (mathematics)|genus]] and [[orientability]] of the supporting surface, the [[Graph embedding|underlying graph]], or the [[automorphism group]].

==Overview==

Regular maps are typically defined and studied in three ways: topologically, group-theoretically, and graph-theoretically.

===Topological approach===
Topologically, a map is a [[Cellular decomposition|2-cell decomposition]] of a compact connected 2-manifold.<ref>{{harvcoltxt|Nedela|2007}}</ref>

The genus g, of a map M is given by [[Euler characteristic|Euler's relation]] <math> \chi (M) = |V| - |E| +|F| </math> which is equal to <math> 2 -2g </math> if the map is orientable, and <math> 2 - g </math> if the map is non-orientable. It is a crucial fact that there is a finite (non-zero) number of regular maps for every orientable genus except the torus.

===Group-theoretical approach===
Group-theoretically, the permutation representation of a regular map ''M'' is a transitive [[permutation group]]&nbsp;''C'', on a set <math>\Omega</math> of [[Flag (geometry)|flags]], generated by three fixed-point free involutions ''r''<sub>0</sub>, ''r''<sub>1</sub>, ''r''<sub>2</sub> satisfying (r<sub>0</sub>r<sub>2</sub>)<sup>2</sup>= I. In this definition the faces are the orbits of ''F''&nbsp;=&nbsp;''<''r<sub>0</sub>,&nbsp;''r''<sub>1</sub>>, edges are the orbits of ''E''&nbsp;=&nbsp;<''r''<sub>0</sub>,&nbsp;''r''<sub>2</sub>>, and vertices are the orbits of ''V''&nbsp;=&nbsp;<''r''<sub>1</sub>,&nbsp;''r''<sub>2</sub>>.  More abstractly, the automorphism group of any regular map is the non-degenerate, homomorphic image of a <2,m,n>-[[triangle group]].

===Graph-theoretical approach===
Graph-theoretically, a map is a cubic graph <math>\Gamma</math> with edges coloured blue, yellow, red such that: <math>\Gamma</math> is connected, every vertex is incident to one edge of each colour, and cycles of edges not coloured yellow have length 4. Note that <math>\Gamma</math> is the ''flag graph'' or [[graph-encoded map]] (GEM) of the map, defined on the vertex set of flags <math>\Omega</math> and is not the skeleton G = (V,E) of the map. In general, |<math>\Omega</math>| = 4|E|.

A map M is regular if Aut(M) [[Group action (mathematics)|acts]] [[Proper action|regularly]] on the flags. Aut(''M'') of a regular map is transitive on the vertices, edges, and faces of&nbsp;''M''.  A map ''M'' is said to be reflexible iff Aut(''M'') is regular and contains an automorphism <math>\phi</math> that fixes both a vertex&nbsp;''v'' and a face&nbsp;''f'', but reverses the order of the edges. A map which is regular but not reflexible is said to be [[Chirality (mathematics)|chiral]].

==Examples==
[[File:Hemicube.svg|thumb|The hemicube, a regular map.]]
* The [[great dodecahedron]] is a regular map with pentagonal faces in the orientable surface of genus 4.
* The [[Hemicube (geometry)|hemicube]] is a regular map of type {4,3} in the [[projective plane]].
* The [[hemi-dodecahedron]] is a regular map produced by pentagonal embedding of the Petersen graph in the projective plane.
* The p-[[hosohedron]] is a regular map of type {2,p}.
* The [[Dyck map]] is a regular map of 12 octagons on a genus-3 surface. Its underlying graph, the [[Dyck graph]], can also form a regular map of 16 hexagons in a torus.

The following is a complete list of regular maps in surfaces of positive [[Euler characteristic]], &chi;: the sphere and the projective plane.<ref>{{harvcoltxt|Coxeter|Moser|1980}}</ref><!--Coxeter gives Schläfli symbols, without names, calls them ''regular tessellations of the elliptic plane (&chi;=1)-->

{| class="wikitable sortable"
|-
![[Euler characteristic|&chi;]]|| [[Genus (mathematics)|g]]|| [[Schläfli symbol|Schläfli]]||Vert.||Edges||Faces || Group||[[Group order|Order]] || colspan=2|Graph || Notes
|- align=center
|2 || 0 || {p,2}||p||p||2 || [[Cyclic group|C<sub>2</sub>]] × [[dihedral group|Dih]]<sub>''p''</sub>||4''p'' || [[Cycle graph|C<sub>''p''</sub>]]||[[File:Undirected 6 cycle.svg|40px]] || [[Dihedron]]
|- align=center
|2 || 0 || {2,p}||2||p||p|| C<sub>2</sub> × Dih<sub>''p''</sub> ||4''p'' || ''p''-fold [[Complete graph|K<sub>2</sub>]]|| || [[Hosohedron]]
|- align=center
|2 || 0 || {3,3}||4||6||4 || [[Symmetric group|S]]<sub>4</sub> ||24 || [[Complete graph|K<sub>4</sub>]]||[[File:3-simplex graph.svg|40px]] || [[Tetrahedron]]
|- align=center
|2 || 0 || {4,3}||8||12||6 || C<sub>2</sub> × S<sub>4</sub> ||48 || [[Complete graph|K<sub>4</sub>]] [[Tensor product of graphs|×]] [[Complete graph|K<sub>2</sub>]]||[[File:3-cube column graph.svg|40px]] || [[Cube]]
|- align=center
|2 || 0 || {3,4}||6||12||8 || C<sub>2</sub> × S<sub>4</sub> ||48 || [[Turán graph|K<sub>2,2,2</sub>]]||[[File:Complex tripartite graph octahedron.svg|40px]] || [[Octahedron]]
|- align=center
|2 || 0 || {5,3}||20||30||12 || C<sub>2</sub> × [[Alternating group|A]]<sub>5</sub>||120 || ||[[File:Dodecahedron H3 projection.svg|40px]] || [[Dodecahedron]]
|- align=center
|2 || 0 || {3,5}||12||30||20 || C<sub>2</sub> × A<sub>5</sub> ||120 || [[Complete graph|K<sub>6</sub>]] [[Tensor product of graphs|×]] [[Complete graph|K<sub>2</sub>]]||[[File:Icosahedron A2 projection.svg|40px]] || [[Icosahedron]]
|- align=center
|1 || n1 || {2p,2}/2||p||p||1 || Dih<sub>2''p''</sub> ||4''p'' || [[Cycle graph|C<sub>''p''</sub>]]|| [[File:Undirected 6 cycle.svg|40px]] || Hemi-dihedron<ref name="csequin">{{harvcoltxt|Séquin|2013}}</ref>
|- align=center
|1 || n1 || {2,2p}/2||2||p||p || Dih<sub>2''p''</sub> ||4''p'' || ''p''-fold [[Complete graph|K<sub>2</sub>]]|| || Hemi-hosohedron<ref name="csequin" />
|- align=center
|1 || n1 || {4,3}/2||4||6||3 || S<sub>4</sub> ||24 || [[Complete graph|K<sub>4</sub>]]||[[File:3-simplex graph.svg|40px]] || [[Hemicube (geometry)|Hemicube]]
|- align=center
|1 || n1 || {3,4}/2||3||6||4 || S<sub>4</sub> ||24 || 2-fold [[Complete graph|K<sub>3</sub>]]|||| [[Hemioctahedron]]
|- align=center
|1 || n1 || {5,3}/2||10||15||6 || A<sub>5</sub> ||60 || [[Petersen graph]]||[[File:Petersen1 tiny.svg|40px]] || [[Hemidodecahedron]]
|- align=center
|1 || n1 || {3,5}/2||6||15||10 || A<sub>5</sub> ||60 || [[Complete graph|K<sub>6</sub>]]||[[File:5-simplex graph.svg|40px]] || [[Hemi-icosahedron]]
|}

The images below show three of the 20 regular maps in the [[triple torus]], labelled with their Schläfli types.
<gallery>
File:R3.4d 6-4 hos.jpg|{{math|{6,4}}}
File:R3.6 4-8 hos.jpg|{{math|{4,8}}}
File:R3.6d 8-4 hos.jpg|{{math|{8,4}}}
</gallery>

==Toroidal polyhedra==
{| class="wikitable" style="float:right;"
|+ Example visualized as nets
|- align=center
|[[File:Regular map 4-4 1-0.png|80px]]<br>{4,4}<sub>1,0</sub><br>(v:1, e:2, f:1)
|[[File:Regular map 4-4 1-1.png|80px]]<br>{4,4}<sub>1,1</sub><br>(v:2, e:4, f:2)
|[[File:Regular map 4-4 2-0.png|80px]]<br>{4,4}<sub>2,0</sub><br>(v:4, e:8, f:4)
|[[File:Regular map 4-4 2-1.png|80px]]<br>{4,4}<sub>2,1</sub><br>(v:5, e:10, f:5)
|[[File:Regular map 4-4 2-2.png|80px]]<br>{4,4}<sub>2,2</sub><br>(v:8, e:16, f:8)
|- align=center
|[[File:Regular map 3-6 1-0.png|80px]]<br>{3,6}<sub>1,0</sub><br>(v:1, e:3, f:2)
|[[File:Regular map 3-6 1-1.png|80px]]<br>{3,6}<sub>1,1</sub><br>(v:3, e:9, f:6)
|[[File:Regular map 3-6 2-0.png|80px]]<br>{3,6}<sub>2,0</sub><br>(v:4, e:12, f:8)
|[[File:Regular map 3-6 2-1.png|80px]]<br>{3,6}<sub>2,1</sub><br>(v:7, e:21, f:14)
|[[File:Regular map 3-6 2-2.png|80px]]<br>{3,6}<sub>2,2</sub><br>(v:12, e:36, f:24)
|- align=center
|[[File:Regular map 6-3 1-0.png|80px]]<br>{6,3}<sub>1,0</sub><br>(v:2, e:3, f:1)
|[[File:Regular map 6-3 1-1.png|80px]]<br>{6,3}<sub>1,1</sub><br>(v:6, e:9, f:3)
|[[File:Regular map 6-3 2-0.png|80px]]<br>{6,3}<sub>2,0</sub><br>(v:8, e:12, f:4)
|[[File:Regular map 6-3 2-1.png|80px]]<br>{6,3}<sub>2,1</sub><br>(v:14, e:21, f:7)
|[[File:Regular map 6-3 2-2.png|80px]]<br>{6,3}<sub>2,2</sub><br>(v:24, e:36, f:12)
|}

Regular maps exist as torohedral polyhedra as finite portions of Euclidean tilings, wrapped onto the surface of a [[duocylinder]] as a [[flat torus]]. These are labeled {4,4}<sub>''b'',''c''</sub> for those related to the [[square tiling]], {4,4}.<ref>[[Coxeter]] 1980, 8.3 Maps of type {4,4} on a torus.</ref> {3,6}<sub>''b'',''c''</sub> are related to the [[triangular tiling]], {3,6}, and {6,3}<sub>''b'',''c''</sub> related to the [[hexagonal tiling]], {6,3}. ''b'' and ''c'' are [[Natural number|whole numbers]].<ref>[[Coxeter]] 1980, 8.4 Maps of type {3,6} or {6,3} on a torus.</ref> There are 2 special cases (''b'',0) and (''b'',''b'') with reflective symmetry, while the general cases exist in chiral pairs (''b'',''c'') and (''c'',''b'').

Regular maps of the form {4,4}<sub>''m'',0</sub> can be represented as the finite [[regular skew polyhedron]] {4,4 | ''m''}, seen as the square faces of a ''m''×''m'' [[duoprism]] in 4-dimensions.

Here's an example {4,4}<sub>8,0</sub> mapped from a plane as a [[chessboard]] to a cylinder section to a torus. The projection from a cylinder to a torus distorts the geometry in 3 dimensions, but can be done without distortion in 4-dimensions.
:[[File:Torus_from_rectangle.gif]]

{| class="wikitable sortable"
|+ Regular maps with zero [[Euler characteristic]]<ref>[[Coxeter]] and Moser, ''Generators and Relations for Discrete Groups'', 1957, Chapter 8, ''Regular maps'', 8.3 Maps of type {4,4} on a torus, 8.4 Maps of type {3,6} or {6,3} on a torus</ref>
|-
![[Euler characteristic|&chi;]]|| [[Genus (mathematics)|g]]|| [[Schläfli symbol|Schläfli]]||Vert.||Edges||Faces || Group||[[Group order|Order]] || Notes
|-  style="background:honeyDew; text-align:center;"
|0||1||{4,4}<sub>''b'',0</sub><br>''n''=''b''<sup>2</sup>||''n''||2''n''||''n''||[4,4]<sub>(''b'',0)</sub>||8''n'' || Flat toroidal polyhedra<br>Same as {4,4 <nowiki>|</nowiki> ''b''}
|-  style="background:honeyDew; text-align:center;"
|0||1||{4,4}<sub>''b'',''b''</sub><br>''n''=2''b''<sup>2</sup>||''n''||2''n''||''n''||[4,4]<sub>(''b'',''b'')</sub> ||8''n'' || Flat toroidal polyhedra<br>Same as rectified {4,4 <nowiki>|</nowiki> ''b''}
|-  style="background:honeyDew; text-align:center;"
|0||1||{4,4}<sub>''b'',''c''</sub><br>''n''=''b''<sup>2</sup>+''c''<sup>2</sup>||''n''||2''n''||''n''||[4,4]{{Supsub|+|<sub>(''b'',''c'')</sub>}} ||4''n'' || Flat chiral toroidal polyhedra
|-  style="background:#fff0f0; text-align:center;"
|0||1||{3,6}<sub>''b'',''0''</sub><br>''t''=''b''<sup>2</sup>||''t''||3''t''||2''t''||[3,6]<sub>(''b'',0)</sub> ||12''t'' || Flat toroidal polyhedra
|-  style="background:#fff0f0; text-align:center;"
|0||1||{3,6}<sub>''b'',''b''</sub><br>''t''=3''b''<sup>2</sup>||''t''||3''t''||2''t''||[3,6]<sub>(''b'',''b'')</sub> ||12''t'' || Flat toroidal polyhedra
|-  style="background:#fff0f0; text-align:center;"
|0||1||{3,6}<sub>''b'',''c''</sub><br>''t''=''b''<sup>2</sup>+''bc''+''c''<sup>2</sup>||''t''||3''t''||2''t''||[3,6]{{Supsub|+|<sub>(''b'',''c'')</sub>}} ||6''t'' || Flat chiral toroidal polyhedra
|-  style="background:#f0f0ff; text-align:center;"
|0||1||{6,3}<sub>''b'',''0''</sub><br>''t''=''b''<sup>2</sup>||2''t''||3''t''||''t''||[3,6]<sub>(''b'',0)</sub> ||12''t'' ||  Flat toroidal polyhedra
|-  style="background:#f0f0ff; text-align:center;"
|0||1||{6,3}<sub>''b'',''b''</sub><br>''t''=3''b''<sup>2</sup>||2''t''||3''t''||''t''||[3,6]<sub>(''b'',''b'')</sub> ||12''t'' ||  Flat toroidal polyhedra
|-  style="background:#f0f0ff; text-align:center;"
|0||1||{6,3}<sub>''b'',''c''</sub><br>''t''=''b''<sup>2</sup>+''bc''+''c''<sup>2</sup>||2''t''||3''t''||''t''||[3,6]{{Supsub|+|<sub>(''b'',''c'')</sub>}} ||6''t'' ||  Flat chiral toroidal polyhedra
|}
In generally regular toroidal polyhedra {''p'',''q''}<sub>''b'',''c''</sub> can be defined if either ''p'' or ''q'' are even, although only euclidean ones above can exist as toroidal polyhedra in 4-dimensions. In {2''p'',''q''}, the paths (''b'',''c'') can be defined as stepping face-edge-face in straight lines, while the dual {''p'',2''q''} forms will see the paths (''b'',''c'') as stepping vertex-edge-vertex in straight lines.

== Hyperbolic regular maps==
{| class=wikitable align=right width=400
|[[File:Octahedron 4 petrie polygons.png|200px]]
|[[File:Regular map 6 4-3 pattern.png|200px]]
|-
|colspan=2|The map {6,4}<sub>3</sub> can be seen as {6,4}<sub>4,0</sub>. Following opposite edges will traverse all 4 hexagons in sequence. It exists in the [[petrial octahedron]], {3,4}<sup>{{pi}}</sup> with 6 vertices, 12 edges and 4 skew hexagon faces.
|}
[[File:Double-cube-regular-map.png|320px|left|thumb|[[Branko Grünbaum]] identified a double-covered cube {8/2,3}, with 6 octagonal faces, double wrapped, needing 24 edges, and 16 vertices. It can be seen as regular map {8,3}<sub>2,0</sub> on a hyperbolic plane with 6 colored octagons.<ref>https://web.archive.org/web/20181126084335/https://sites.math.washington.edu/~grunbaum/Your%20polyhedra-my%20polyhedra.pdf {{Bare URL PDF|date=August 2024}}</ref>]]
{{clear}}

== See also ==
*[[Topological graph theory]]
*[[Abstract polytope]]
*[[Planar graph]]
*[[Toroidal graph]]
*[[Graph embedding]]
*[[Regular tiling]]
*[[Platonic solid]]
*[[Platonic graph]]

== References ==
{{Reflist}}

== Bibliography ==
* {{citation
 | last1 = Coxeter | first1 = H. S. M. | author1-link = Harold Scott MacDonald Coxeter
 | last2 = Moser | first2 = W. O. J.
 | edition = 4th
 | isbn = 978-0-387-09212-6
 | publisher = Springer Verlag
 | series = Ergebnisse der Mathematik und ihrer Grenzgebiete
 | title = Generators and Relations for Discrete Groups
 | volume = 14
 | year = 1980}}.
*{{citation
 |last        = van Wijk
 |first       = Jarke J.
 |author-link  = Jack van Wijk
 |title = Symmetric tiling of closed surfaces: Visualization of regular maps
 |journal = ACM Transactions on Graphics
 |department = Proc. SIGGRAPH
 |doi         = 10.1145/1531326.1531355
 |article-number = 49
 |pages        = 1–12
 |issue       = 3
 |url         = http://www.win.tue.nl/~vanwijk/regularmaps_siggraph09.pdf
 |volume      = 28
 |year        = 2009
 |url-status = dead
 |archive-url  = https://web.archive.org/web/20110609013201/http://www.win.tue.nl/~vanwijk/regularmaps_siggraph09.pdf
 |archive-date = 2011-06-09
}}.
*{{citation
 | last1 = Conder | first1 = Marston | author1-link = Marston Conder
 | last2 = Dobcsányi | first2 = Peter
 | doi = 10.1006/jctb.2000.2008 | doi-access=free
 | issue = 2
 | journal = [[Journal of Combinatorial Theory, Series B]]
 | pages = 224–242
 | title = Determination of all regular maps of small genus
 | volume = 81
 | year = 2001}}. 
*{{citation
 | last = Nedela
 | first = Roman
 | title = Maps, Hypermaps, and Related Topics
 | url = http://www.savbb.sk/~nedela/CMbook.pdf
 | year = 2007
 | access-date = 2009-08-31
 | archive-date = 2016-03-04
 | archive-url = https://web.archive.org/web/20160304093723/http://www.savbb.sk/~nedela/CMbook.pdf
 | url-status = dead
 }}.
*{{citation
 | last = Vince | first = Andrew
 | contribution = Maps
 | title = Handbook of Graph Theory
 | year = 2004}}. 
*{{citation
 | last1 = Brehm | first1 = Ulrich
 | last2 = Schulte | first2 = Egon
 | contribution = Polyhedral Maps
 | title = Handbook of Discrete and Computational Geometry
 | year = 2004}}.
*{{citation
 | last1 = Séquin | first1 = Carlo
 | title = Symmetrical immersions of low-genus non-orientable regular maps
 | url = http://www.cs.berkeley.edu/~sequin/PAPERS/2013_Symm-Fest_NonOrRegMaps.pdf
 | website = Berkeley University
 | year = 2013
 }}.

[[Category:Topological graph theory]]
[[Category:Discrete geometry]]