Premium
Crossing numbers of sequences of graphs II: Planar tiles
Author(s) -
Pitoan Benny,
Richter R. Bruce
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10097
Subject(s) - mathematics , combinatorics , planar graph , tile , book embedding , rational number , 1 planar graph , planar , graph , pathwidth , discrete mathematics , sequence (biology) , crossing number (knot theory) , indifference graph , chordal graph , line graph , computer science , art , computer graphics (images) , intersection (aeronautics) , biology , engineering , visual arts , genetics , aerospace engineering
We describe a method of creating an infinite family of crossing‐critical graphs from a single small planar map, the tile , by gluing together many copies of the tile together in a circular fashion. This method yields all known infinite families of k ‐crossing‐critical graphs. Furthermore, the method yields new infinite families, which extend from (4,6) to (3.5,6) the interval of rationals r for which there is, for some k , an infinite sequence of k ‐crossing‐critical graphs all having average degree r . © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 332–341, 2003