Zeichnung und Einbettung eines Graphen

Eine Zeichnung (Einbettung in die Ebene) ist eine topologische Abbildung, die ein abstraktes kombinatorisches Graphennetzwerk in den zweidimensionalen geometrischen Raum überführt.

• Formale Definition: Eine Abbildung $\pi$, die jedem Knoten $v\in V(G)$ einen eindeutigen Punkt $\pi (v)\in {\mathbb{R}}^2$ und jeder Kante $e=\{u,v\}\in E(G)$ eine kontinuierliche Kurve $\pi (e)\subseteq {\mathbb{R}}^2$ zuordnet.
• Randbedingungen: Die Kurve $\pi (e)$ verbindet die Punkte $\pi (u)$ und $\pi (v)$ und darf keinen weiteren Knotenpunkt $\pi (x)$ für ein $x\in V(G)\setminus \{u,v\}$ schneiden oder enthalten.

Links

• DS_vollständiger_foliensatz.pdf