© h.hofstede (h.hofstede@hogeland.nl)

Een Tekenvoorschrift.
   
De grote vraag is:  Als je vermoedt dat een graaf planair is, maar hij ziet er nogal ingewikkeld uit, hoe verzin je dan een manier om hem ook planair te tekenen?

Nog even een term:
Een brug van een graaf kan "in een facet getekend worden" als alle aanknopingspunten van die brug ook randpunten van dat facet zijn.

Daarmee is dit zo'n recept:

 
1. Begin met een willekeurige cykel in G en noem die G1.
2. Tel bij elke brug van G1 in hoeveel facetten van G1 die brug getekend kan worden.
3. Als er eentje is met 0 dan is de graaf niet planair, en kun je stoppen
4. Als er bruggen met 1 zijn, dan moet je daar eentje van kiezen. Als ze allemaal meer dan 1 zijn kies er dan zomaar eentje
5. Kies een route in B tussen twee aanknooppunten. En teken die route in een facet van G1
5. Voeg de route toe aan  G1;  dat geeft de volgende variant  G2.
6. Ga naar stap 2, maar nu met G2.
       
Dit recept loopt óf  (in stap 3) vast, en dan is de graaf niet planair,  óf het levert uiteindelijk een planaire tekening van de graaf op.

Een voorbeeld van het recept in werking:
       
1. We kiezen eerst willekeurig van graaf G hiernaast de rode cykel  ABEFGHA.
 
2. Die heeft vier bruggen; hiernaast elk met een andere kleur getekend  (blauw, groen, paars en bruin).  In hoeveel facetten kunnen ze getekend worden?
G1 heeft nog maar 2 facetten (binnenkant en buitenkant). Ga na dat al die bruggen in beide facetten te tekenen zijn.
We kiezen er zomaar eentje,  bijvoorbeeld de groene brug, en we tekenen de route HIB bijvoorbeeld in het binnengebied van G1 om G2 te krijgen.
 

3. G2 heeft nu drie facetten (ABIHA, HIBEFGH en het buitengebied)
De paarse en de bruine brug kunnen nog steeds in 2 facetten worden getekend, maar de blauwe niet: die kan alleen in het buitengebied worden getekend, dus die moeten we nu kiezen om toe te voegen aan G2.
Voeg bijvoorbeeld route BCDE toe aan G2.
Dat geeft  G3.

4. G3  heeft nu 4 facetten (3 plus buitengebied) en nog 3 bruggen.
De blauwe brug kan nog maar in één facet getekend worden (namelijk het buitengebied)
Dat geeft  G4.

5. G4  heeft nog 2 bruggen die beiden nog maar in één facet getekend kunnen worden. Kies bijvoorbeeld de paarse brug en voeg route HJB toe aan G4 om G5 te krijgen.

6. De paarse brug is in drie bruggen uit elkaar gevallen.
Nu kan brug BG  alleen nog maar in het buitengebied getekend worden, dus doen we dat.  Dat geeft  G6.

7. Brug HF kan alleen nog maar in facet HGFEBJH maar daarna kan GJ niet meer worden getekend.

Het kleuralgoritme loopt vast;  de graaf is niet planair.
       

© h.hofstede (h.hofstede@hogeland.nl)