20:
655:
represent each of these three types of flags that differ by one of their three elements. However, interpreting a graph-encoded map in this way requires more care. When the same face appears on both sides of an edge, as can happen for instance for a planar embedding of a
728:
can be 3-edge-colored so that the red-blue cycles of the coloring all have length four, the colored graph can be interpreted as a graph-encoded map, and represents an embedding of another graph
633:
590:
547:
700:
504:
479:
454:
429:
324:
854:
834:
806:
786:
766:
746:
726:
653:
391:
367:
344:
299:
279:
259:
239:
219:
199:
179:
159:
139:
115:
92:
863:
of a graph-encoded map may be obtained from the map by recoloring it so that the red edges of the gem become blue and the blue edges become red.
983:
906:
44:
28:
23:
A graph-encoded map (gray triangles and colored edges) of a graph in the plane (white circles and black edges)
660:, the two sides give rise to different gem vertices. And when the same vertex appears at both endpoints of a
657:
809:
664:, the two ends of the edge again give rise to different gem vertices. In this way, each triple
902:
595:
552:
509:
888:
836:, and replace each pair of parallel blue edges left by the contraction with a single edge of
667:
396:
938:
894:
813:
221:
connects each such vertex to the vertex representing the opposite side and same endpoint of
952:
916:
948:
912:
370:
64:
40:
301:
of the third color, yellow, connects each vertex to the vertex representing another edge
63:. Alternative and equivalent systems for representing cellular embeddings include signed
484:
459:
434:
304:
839:
819:
791:
771:
751:
731:
711:
638:
376:
352:
329:
284:
264:
261:
connects each vertex to the vertex representing the opposite endpoint and same side of
244:
224:
204:
184:
164:
144:
124:
100:
77:
977:
943:
118:
47:
using a different graph with four vertices per edge of the original graph. It is the
68:
706:
95:
52:
19:
898:
860:
56:
661:
48:
201:, one for each choice of a side and endpoint of the edge. An edge in
18:
702:
may be associated with up to four different vertices of the gem.
393:(a mutually incident triple of a vertex, edge, and face). If
241:; these edges are by convention colored red. Another edge in
281:; these edges are by convention colored blue. An edge in
842:
822:
794:
774:
768:
and its embedding, interpret each 2-colored cycle of
754:
734:
714:
670:
641:
598:
555:
512:
487:
462:
437:
399:
379:
355:
332:
307:
287:
267:
247:
227:
207:
187:
167:
147:
127:
103:
80:
887:Bonnington, C. Paul; Little, Charles H. C. (1995),
848:
828:
800:
780:
760:
740:
720:
694:
647:
627:
584:
541:
498:
473:
448:
423:
385:
361:
338:
318:
293:
273:
253:
233:
213:
193:
173:
153:
133:
109:
86:
59:. Graph-encoded maps were formulated and named by
964:
816:each red--yellow cycle into a single vertex of
929:Lins, Sóstenes (1982), "Graph-encoded maps",
635:are also flags. The three colors of edges in
8:
431:is a flag, then there is exactly one vertex
74:The graph-encoded map for an embedded graph
890:The foundations of topological graph theory
181:is expanded into exactly four vertices in
942:
893:, New York: Springer-Verlag, p. 31,
841:
821:
793:
773:
753:
733:
713:
669:
640:
597:
554:
511:
486:
461:
436:
398:
378:
354:
331:
306:
286:
266:
246:
226:
206:
186:
166:
146:
126:
102:
79:
16:Graph describing a topological embedding
872:
7:
882:
880:
878:
876:
60:
14:
369:is that it has a vertex for each
931:Journal of Combinatorial Theory
788:as the face of an embedding of
346:at the same side and endpoint.
965:Bonnington & Little (1995)
689:
671:
622:
599:
579:
556:
536:
513:
418:
400:
349:An alternative description of
1:
944:10.1016/0095-8956(82)90033-8
55:, a geometric operation on
1000:
39:is a method of encoding a
899:10.1007/978-1-4612-2540-9
984:Topological graph theory
628:{\displaystyle (v,e,f')}
585:{\displaystyle (v,e',f)}
542:{\displaystyle (v',e,f)}
29:topological graph theory
695:{\displaystyle (v,e,f)}
424:{\displaystyle (v,e,f)}
850:
830:
802:
782:
762:
742:
722:
696:
649:
629:
586:
543:
500:
475:
450:
425:
387:
363:
340:
320:
295:
275:
255:
235:
215:
195:
175:
155:
135:
111:
88:
24:
851:
831:
803:
783:
763:
743:
723:
697:
650:
630:
587:
544:
501:
476:
451:
426:
388:
364:
341:
321:
296:
276:
256:
236:
216:
196:
176:
156:
136:
112:
89:
22:
840:
820:
792:
772:
752:
732:
712:
668:
639:
596:
553:
510:
485:
460:
435:
397:
377:
353:
330:
305:
285:
265:
245:
225:
205:
185:
165:
145:
125:
101:
78:
967:, pp. 111–112.
846:
826:
798:
778:
758:
738:
718:
692:
645:
625:
582:
539:
499:{\displaystyle f'}
496:
474:{\displaystyle e'}
471:
449:{\displaystyle v'}
446:
421:
383:
359:
336:
319:{\displaystyle e'}
316:
291:
271:
251:
231:
211:
191:
171:
151:
131:
107:
84:
41:cellular embedding
25:
849:{\displaystyle G}
829:{\displaystyle G}
801:{\displaystyle H}
781:{\displaystyle H}
761:{\displaystyle G}
741:{\displaystyle G}
721:{\displaystyle H}
648:{\displaystyle H}
386:{\displaystyle G}
362:{\displaystyle H}
339:{\displaystyle e}
294:{\displaystyle H}
274:{\displaystyle e}
254:{\displaystyle H}
234:{\displaystyle e}
214:{\displaystyle H}
194:{\displaystyle H}
174:{\displaystyle G}
154:{\displaystyle e}
134:{\displaystyle H}
110:{\displaystyle H}
87:{\displaystyle G}
33:graph-encoded map
991:
968:
962:
956:
955:
946:
926:
920:
919:
884:
855:
853:
852:
847:
835:
833:
832:
827:
807:
805:
804:
799:
787:
785:
784:
779:
767:
765:
764:
759:
747:
745:
744:
739:
727:
725:
724:
719:
701:
699:
698:
693:
654:
652:
651:
646:
634:
632:
631:
626:
621:
591:
589:
588:
583:
572:
548:
546:
545:
540:
523:
505:
503:
502:
497:
495:
480:
478:
477:
472:
470:
455:
453:
452:
447:
445:
430:
428:
427:
422:
392:
390:
389:
384:
368:
366:
365:
360:
345:
343:
342:
337:
325:
323:
322:
317:
315:
300:
298:
297:
292:
280:
278:
277:
272:
260:
258:
257:
252:
240:
238:
237:
232:
220:
218:
217:
212:
200:
198:
197:
192:
180:
178:
177:
172:
160:
158:
157:
152:
140:
138:
137:
132:
117:together with a
116:
114:
113:
108:
93:
91:
90:
85:
65:rotation systems
999:
998:
994:
993:
992:
990:
989:
988:
974:
973:
972:
971:
963:
959:
928:
927:
923:
909:
886:
885:
874:
869:
838:
837:
818:
817:
790:
789:
770:
769:
750:
749:
730:
729:
710:
709:
666:
665:
637:
636:
614:
594:
593:
565:
551:
550:
516:
508:
507:
488:
483:
482:
463:
458:
457:
438:
433:
432:
395:
394:
375:
374:
351:
350:
328:
327:
308:
303:
302:
283:
282:
263:
262:
243:
242:
223:
222:
203:
202:
183:
182:
163:
162:
143:
142:
123:
122:
119:3-edge-coloring
99:
98:
76:
75:
17:
12:
11:
5:
997:
995:
987:
986:
976:
975:
970:
969:
957:
937:(2): 171–181,
921:
907:
871:
870:
868:
865:
845:
825:
797:
777:
757:
737:
717:
691:
688:
685:
682:
679:
676:
673:
644:
624:
620:
617:
613:
610:
607:
604:
601:
581:
578:
575:
571:
568:
564:
561:
558:
538:
535:
532:
529:
526:
522:
519:
515:
494:
491:
469:
466:
444:
441:
420:
417:
414:
411:
408:
405:
402:
382:
358:
335:
314:
311:
290:
270:
250:
230:
210:
190:
170:
150:
130:
106:
83:
15:
13:
10:
9:
6:
4:
3:
2:
996:
985:
982:
981:
979:
966:
961:
958:
954:
950:
945:
940:
936:
932:
925:
922:
918:
914:
910:
908:0-387-94557-1
904:
900:
896:
892:
891:
883:
881:
879:
877:
873:
866:
864:
862:
857:
843:
823:
815:
811:
795:
775:
755:
748:. To recover
735:
715:
708:
703:
686:
683:
680:
677:
674:
663:
659:
642:
618:
615:
611:
608:
605:
602:
576:
573:
569:
566:
562:
559:
533:
530:
527:
524:
520:
517:
492:
489:
467:
464:
442:
439:
415:
412:
409:
406:
403:
380:
372:
356:
347:
333:
312:
309:
288:
268:
248:
228:
208:
188:
168:
148:
128:
120:
104:
97:
81:
72:
70:
69:ribbon graphs
66:
62:
58:
54:
50:
46:
42:
38:
34:
30:
21:
960:
934:
933:, Series B,
930:
924:
889:
858:
704:
348:
141:. Each edge
73:
51:analogue of
36:
32:
26:
707:cubic graph
705:Whenever a
481:, and face
326:that meets
96:cubic graph
94:is another
61:Lins (1982)
53:runcination
49:topological
867:References
861:dual graph
506:such that
662:self-loop
57:polyhedra
978:Category
814:contract
619:′
570:′
521:′
493:′
468:′
443:′
313:′
953:0657686
917:1367285
810:surface
808:onto a
456:, edge
951:
915:
905:
592:, and
45:graph
43:of a
903:ISBN
859:The
658:tree
371:flag
67:and
31:, a
939:doi
895:doi
373:of
161:of
121:of
37:gem
35:or
27:In
980::
949:MR
947:,
935:32
913:MR
911:,
901:,
875:^
856:.
812:,
549:,
71:.
941::
897::
844:G
824:G
796:H
776:H
756:G
736:G
716:H
690:)
687:f
684:,
681:e
678:,
675:v
672:(
643:H
623:)
616:f
612:,
609:e
606:,
603:v
600:(
580:)
577:f
574:,
567:e
563:,
560:v
557:(
537:)
534:f
531:,
528:e
525:,
518:v
514:(
490:f
465:e
440:v
419:)
416:f
413:,
410:e
407:,
404:v
401:(
381:G
357:H
334:e
310:e
289:H
269:e
249:H
229:e
209:H
189:H
169:G
149:e
129:H
105:H
82:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
