Formal definition of “planar graph”












8












$begingroup$


The wikipedia definition of "planar graph" says:




In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.




I think this is a quite good description, and one quickly understands what is meant by "planar graph". But to me, the definition seems to be informal. How can one formally define the concepts "drawing on the plane" and "the edges don't cross"?






graph-theory soft-question definition plane-geometry







share|cite|improve this question









$endgroup$








  • 2




    $begingroup$
    This definition is not informal, it's the actual definition.
    $endgroup$
    – Crostul
    3 hours ago






  • 3




    $begingroup$
    @Crostul: I agree that it's the actual definition. But I still think that it's informal.
    $endgroup$
    – user7280899
    2 hours ago
















8












$begingroup$


The wikipedia definition of "planar graph" says:




In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.




I think this is a quite good description, and one quickly understands what is meant by "planar graph". But to me, the definition seems to be informal. How can one formally define the concepts "drawing on the plane" and "the edges don't cross"?






graph-theory soft-question definition plane-geometry







share|cite|improve this question









$endgroup$








  • 2




    $begingroup$
    This definition is not informal, it's the actual definition.
    $endgroup$
    – Crostul
    3 hours ago






  • 3




    $begingroup$
    @Crostul: I agree that it's the actual definition. But I still think that it's informal.
    $endgroup$
    – user7280899
    2 hours ago














8












8








8


2



$begingroup$


The wikipedia definition of "planar graph" says:




In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.




I think this is a quite good description, and one quickly understands what is meant by "planar graph". But to me, the definition seems to be informal. How can one formally define the concepts "drawing on the plane" and "the edges don't cross"?






graph-theory soft-question definition plane-geometry







share|cite|improve this question









$endgroup$




The wikipedia definition of "planar graph" says:




In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.




I think this is a quite good description, and one quickly understands what is meant by "planar graph". But to me, the definition seems to be informal. How can one formally define the concepts "drawing on the plane" and "the edges don't cross"?






graph-theory soft-question definition plane-geometry




graph-theory soft-question definition plane-geometry






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 3 hours ago









user7280899user7280899

854416




854416








  • 2




    $begingroup$
    This definition is not informal, it's the actual definition.
    $endgroup$
    – Crostul
    3 hours ago






  • 3




    $begingroup$
    @Crostul: I agree that it's the actual definition. But I still think that it's informal.
    $endgroup$
    – user7280899
    2 hours ago














  • 2




    $begingroup$
    This definition is not informal, it's the actual definition.
    $endgroup$
    – Crostul
    3 hours ago






  • 3




    $begingroup$
    @Crostul: I agree that it's the actual definition. But I still think that it's informal.
    $endgroup$
    – user7280899
    2 hours ago








2




2




$begingroup$
This definition is not informal, it's the actual definition.
$endgroup$
– Crostul
3 hours ago




$begingroup$
This definition is not informal, it's the actual definition.
$endgroup$
– Crostul
3 hours ago




3




3




$begingroup$
@Crostul: I agree that it's the actual definition. But I still think that it's informal.
$endgroup$
– user7280899
2 hours ago




$begingroup$
@Crostul: I agree that it's the actual definition. But I still think that it's informal.
$endgroup$
– user7280899
2 hours ago










1 Answer
1






active

oldest

votes


















12












$begingroup$

There are a number of ways. For example, we could have an injective function $f : V(G) to mathbb R^2$ giving the coordinates of the vertices. For every edge $vw in E(G)$, we could have a path from $f(v)$ to $f(w)$: a continuous function $h_{vw} : [0,1] to mathbb R^2$ with $h_{vw}(0) = f(v)$ and $h_{vw}(1) = f(w)$. To ensure that the edges don't cross, we could require that for two edges $e_1, e_2$ the corresponding functions $h_1$, $h_2$ don't have $h_1(s) = h_2(t)$ unless both $s$ and $t$ are either $0$ or $1$.



Because the specific topological definition doesn't affect the combinatorial meaning too much, we can play around with this definition to get something easier to work with. For example, rather than making $h_{vw}$ continuous, we could ask for it to be smooth, or piecewise linear. The goal would be to make it easier to prove obvious-sounding geometrical properties of the embedding. For example, you might not want to invoke the Jordan curve theorem just to say that every cycle in the graph has an inside and an outside.



Ultimately, we leave these details out of the definition because the details don't matter much - various ways to fill in the details produce the same notion of planar graphs.



In fact, since every planar graph has a straight-line embedding, we could even make the edges be line segments $[f(v), f(w)]$ and require their interiors to be disjoint. But this is probably less convenient to work with.






share|cite|improve this answer











$endgroup$









  • 2




    $begingroup$
    I see, thank you very much! I agree that it's good to leave the details out of the definition. But it's definitely good to once think about how it could be formalized.
    $endgroup$
    – user7280899
    2 hours ago












  • $begingroup$
    Also, $f$ has to be injective.
    $endgroup$
    – Paul
    1 hour ago










  • $begingroup$
    How hard is it to prove that every planar graph has a straight-line embedding?
    $endgroup$
    – Jason DeVito
    42 mins ago










  • $begingroup$
    @Paul Thanks, fixed.
    $endgroup$
    – Misha Lavrov
    40 mins ago










  • $begingroup$
    @JasonDeVito Wikipedia's article on Fáry's theorem has a proof; it isn't long.
    $endgroup$
    – Misha Lavrov
    39 mins ago











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3073581%2fformal-definition-of-planar-graph%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









12












$begingroup$

There are a number of ways. For example, we could have an injective function $f : V(G) to mathbb R^2$ giving the coordinates of the vertices. For every edge $vw in E(G)$, we could have a path from $f(v)$ to $f(w)$: a continuous function $h_{vw} : [0,1] to mathbb R^2$ with $h_{vw}(0) = f(v)$ and $h_{vw}(1) = f(w)$. To ensure that the edges don't cross, we could require that for two edges $e_1, e_2$ the corresponding functions $h_1$, $h_2$ don't have $h_1(s) = h_2(t)$ unless both $s$ and $t$ are either $0$ or $1$.



Because the specific topological definition doesn't affect the combinatorial meaning too much, we can play around with this definition to get something easier to work with. For example, rather than making $h_{vw}$ continuous, we could ask for it to be smooth, or piecewise linear. The goal would be to make it easier to prove obvious-sounding geometrical properties of the embedding. For example, you might not want to invoke the Jordan curve theorem just to say that every cycle in the graph has an inside and an outside.



Ultimately, we leave these details out of the definition because the details don't matter much - various ways to fill in the details produce the same notion of planar graphs.



In fact, since every planar graph has a straight-line embedding, we could even make the edges be line segments $[f(v), f(w)]$ and require their interiors to be disjoint. But this is probably less convenient to work with.






share|cite|improve this answer











$endgroup$









  • 2




    $begingroup$
    I see, thank you very much! I agree that it's good to leave the details out of the definition. But it's definitely good to once think about how it could be formalized.
    $endgroup$
    – user7280899
    2 hours ago












  • $begingroup$
    Also, $f$ has to be injective.
    $endgroup$
    – Paul
    1 hour ago










  • $begingroup$
    How hard is it to prove that every planar graph has a straight-line embedding?
    $endgroup$
    – Jason DeVito
    42 mins ago










  • $begingroup$
    @Paul Thanks, fixed.
    $endgroup$
    – Misha Lavrov
    40 mins ago










  • $begingroup$
    @JasonDeVito Wikipedia's article on Fáry's theorem has a proof; it isn't long.
    $endgroup$
    – Misha Lavrov
    39 mins ago
















12












$begingroup$

There are a number of ways. For example, we could have an injective function $f : V(G) to mathbb R^2$ giving the coordinates of the vertices. For every edge $vw in E(G)$, we could have a path from $f(v)$ to $f(w)$: a continuous function $h_{vw} : [0,1] to mathbb R^2$ with $h_{vw}(0) = f(v)$ and $h_{vw}(1) = f(w)$. To ensure that the edges don't cross, we could require that for two edges $e_1, e_2$ the corresponding functions $h_1$, $h_2$ don't have $h_1(s) = h_2(t)$ unless both $s$ and $t$ are either $0$ or $1$.



Because the specific topological definition doesn't affect the combinatorial meaning too much, we can play around with this definition to get something easier to work with. For example, rather than making $h_{vw}$ continuous, we could ask for it to be smooth, or piecewise linear. The goal would be to make it easier to prove obvious-sounding geometrical properties of the embedding. For example, you might not want to invoke the Jordan curve theorem just to say that every cycle in the graph has an inside and an outside.



Ultimately, we leave these details out of the definition because the details don't matter much - various ways to fill in the details produce the same notion of planar graphs.



In fact, since every planar graph has a straight-line embedding, we could even make the edges be line segments $[f(v), f(w)]$ and require their interiors to be disjoint. But this is probably less convenient to work with.






share|cite|improve this answer











$endgroup$









  • 2




    $begingroup$
    I see, thank you very much! I agree that it's good to leave the details out of the definition. But it's definitely good to once think about how it could be formalized.
    $endgroup$
    – user7280899
    2 hours ago












  • $begingroup$
    Also, $f$ has to be injective.
    $endgroup$
    – Paul
    1 hour ago










  • $begingroup$
    How hard is it to prove that every planar graph has a straight-line embedding?
    $endgroup$
    – Jason DeVito
    42 mins ago










  • $begingroup$
    @Paul Thanks, fixed.
    $endgroup$
    – Misha Lavrov
    40 mins ago










  • $begingroup$
    @JasonDeVito Wikipedia's article on Fáry's theorem has a proof; it isn't long.
    $endgroup$
    – Misha Lavrov
    39 mins ago














12












12








12





$begingroup$

There are a number of ways. For example, we could have an injective function $f : V(G) to mathbb R^2$ giving the coordinates of the vertices. For every edge $vw in E(G)$, we could have a path from $f(v)$ to $f(w)$: a continuous function $h_{vw} : [0,1] to mathbb R^2$ with $h_{vw}(0) = f(v)$ and $h_{vw}(1) = f(w)$. To ensure that the edges don't cross, we could require that for two edges $e_1, e_2$ the corresponding functions $h_1$, $h_2$ don't have $h_1(s) = h_2(t)$ unless both $s$ and $t$ are either $0$ or $1$.



Because the specific topological definition doesn't affect the combinatorial meaning too much, we can play around with this definition to get something easier to work with. For example, rather than making $h_{vw}$ continuous, we could ask for it to be smooth, or piecewise linear. The goal would be to make it easier to prove obvious-sounding geometrical properties of the embedding. For example, you might not want to invoke the Jordan curve theorem just to say that every cycle in the graph has an inside and an outside.



Ultimately, we leave these details out of the definition because the details don't matter much - various ways to fill in the details produce the same notion of planar graphs.



In fact, since every planar graph has a straight-line embedding, we could even make the edges be line segments $[f(v), f(w)]$ and require their interiors to be disjoint. But this is probably less convenient to work with.






share|cite|improve this answer











$endgroup$



There are a number of ways. For example, we could have an injective function $f : V(G) to mathbb R^2$ giving the coordinates of the vertices. For every edge $vw in E(G)$, we could have a path from $f(v)$ to $f(w)$: a continuous function $h_{vw} : [0,1] to mathbb R^2$ with $h_{vw}(0) = f(v)$ and $h_{vw}(1) = f(w)$. To ensure that the edges don't cross, we could require that for two edges $e_1, e_2$ the corresponding functions $h_1$, $h_2$ don't have $h_1(s) = h_2(t)$ unless both $s$ and $t$ are either $0$ or $1$.



Because the specific topological definition doesn't affect the combinatorial meaning too much, we can play around with this definition to get something easier to work with. For example, rather than making $h_{vw}$ continuous, we could ask for it to be smooth, or piecewise linear. The goal would be to make it easier to prove obvious-sounding geometrical properties of the embedding. For example, you might not want to invoke the Jordan curve theorem just to say that every cycle in the graph has an inside and an outside.



Ultimately, we leave these details out of the definition because the details don't matter much - various ways to fill in the details produce the same notion of planar graphs.



In fact, since every planar graph has a straight-line embedding, we could even make the edges be line segments $[f(v), f(w)]$ and require their interiors to be disjoint. But this is probably less convenient to work with.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 41 mins ago

























answered 3 hours ago









Misha LavrovMisha Lavrov

44.7k556107




44.7k556107








  • 2




    $begingroup$
    I see, thank you very much! I agree that it's good to leave the details out of the definition. But it's definitely good to once think about how it could be formalized.
    $endgroup$
    – user7280899
    2 hours ago












  • $begingroup$
    Also, $f$ has to be injective.
    $endgroup$
    – Paul
    1 hour ago










  • $begingroup$
    How hard is it to prove that every planar graph has a straight-line embedding?
    $endgroup$
    – Jason DeVito
    42 mins ago










  • $begingroup$
    @Paul Thanks, fixed.
    $endgroup$
    – Misha Lavrov
    40 mins ago










  • $begingroup$
    @JasonDeVito Wikipedia's article on Fáry's theorem has a proof; it isn't long.
    $endgroup$
    – Misha Lavrov
    39 mins ago














  • 2




    $begingroup$
    I see, thank you very much! I agree that it's good to leave the details out of the definition. But it's definitely good to once think about how it could be formalized.
    $endgroup$
    – user7280899
    2 hours ago












  • $begingroup$
    Also, $f$ has to be injective.
    $endgroup$
    – Paul
    1 hour ago










  • $begingroup$
    How hard is it to prove that every planar graph has a straight-line embedding?
    $endgroup$
    – Jason DeVito
    42 mins ago










  • $begingroup$
    @Paul Thanks, fixed.
    $endgroup$
    – Misha Lavrov
    40 mins ago










  • $begingroup$
    @JasonDeVito Wikipedia's article on Fáry's theorem has a proof; it isn't long.
    $endgroup$
    – Misha Lavrov
    39 mins ago








2




2




$begingroup$
I see, thank you very much! I agree that it's good to leave the details out of the definition. But it's definitely good to once think about how it could be formalized.
$endgroup$
– user7280899
2 hours ago






$begingroup$
I see, thank you very much! I agree that it's good to leave the details out of the definition. But it's definitely good to once think about how it could be formalized.
$endgroup$
– user7280899
2 hours ago














$begingroup$
Also, $f$ has to be injective.
$endgroup$
– Paul
1 hour ago




$begingroup$
Also, $f$ has to be injective.
$endgroup$
– Paul
1 hour ago












$begingroup$
How hard is it to prove that every planar graph has a straight-line embedding?
$endgroup$
– Jason DeVito
42 mins ago




$begingroup$
How hard is it to prove that every planar graph has a straight-line embedding?
$endgroup$
– Jason DeVito
42 mins ago












$begingroup$
@Paul Thanks, fixed.
$endgroup$
– Misha Lavrov
40 mins ago




$begingroup$
@Paul Thanks, fixed.
$endgroup$
– Misha Lavrov
40 mins ago












$begingroup$
@JasonDeVito Wikipedia's article on Fáry's theorem has a proof; it isn't long.
$endgroup$
– Misha Lavrov
39 mins ago




$begingroup$
@JasonDeVito Wikipedia's article on Fáry's theorem has a proof; it isn't long.
$endgroup$
– Misha Lavrov
39 mins ago


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3073581%2fformal-definition-of-planar-graph%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Knooppunt Holsloot

Image
Knooppunt Holsloot Kenmerken Wegen A37 × N34 Type knooppunt klaverblad Portaal     Verkeer & Vervoer Knooppunt Holsloot is een verkeersknooppunt op de kruising van de autosnelweg A37 en de N34 in Drenthe, tussen Emmen en Coevorden. Oorspronkelijk was deze aansluiting een afritconstructie van het type Haarlemmermeeraansluiting, zoals bij Knooppunt Hooipolder. Sinds 2002 is het knooppunt omgebouwd tot een volledig klaverblad. Als noviteit werd hier voor het eerst gebruikgemaakt van dimbare verlichting in plaats van de normale vaste tijden waarop de verlichting aan en uit gaat, wat een grote kostenbesparing opleverde. [1] Dat Holsloot als volwaardig knooppunt is uitgevoerd, waarbij alle verkeersstromen en afbuigingen ononderbroken kunnen doorgaan, is uitzonderlijk. Het betreft hier namelijk een aansluiting tussen een autosnelweg en niet-snelweg. Een vergelijkbare situatie treft men nabij Hoensbroek bij het knooppunt Ten Esschen.     Aa
Read more

Altaar (religie)

Image
Deel van de serie over kerkelijk gerei waaronder paramenten en liturgisch vaatwerk gebruikt in de liturgie Liturgisch vaatwerk Vasa sacra Miskelk · Pateen Kelklepeltje Ciborie · Monstrans Pyxis · Custodiale Vasa non sacra Ampullen · Wijwatervat Olievaatje Wierookvat · Ablutievat Paramenten Amict · Albe · Baarkleed · Cingel Tuniek · Dalmatiek · Fanon Kazuifel · Manipel · Stola Gremiale · Benedictievelum Mijter Koorkledij Rochet · Superplie Koorkap · Cappa magna Kovel Kelkgerei Bursa · Kelkvelum Ciborievelum Kerklinnen Corporale · Kelkdoekje Lavabodoekje · Palla Altaardwaal Kerkinterieur Altaar · Ambo Biechtstoel · Communiebank Doksaal · Doopvont Faldistorium Godslamp · Hoogaltaar Heilig Kruisaltaar Katheder · Preekstoel Sedilia Tabernakel · Volksaltaar Liturgische boeken Altaarmissaal Benedictionale · Brevier Evangeliarium · Evangelistarium Graduale · Kyriale Lectionarium Psalter · Rituaal Sacramentarium · Volksmissaal Overige Flambou
Read more

Gregoriusmis

Image
Een afbeelding van de Gregoriusmis uit een getijdenboek gemaakt in de zuidelijke Nederlanden tussen 1500 en 1525 Gregoriusmis, Meester van het Akense Altaar, ca. 1500-1525. Collectie Museum Catharijneconvent De Gregoriusmis of de Mis van Sint Gregorius is een motief in katholieke kunst, dat het eerst verscheen in de late Middeleeuwen en dat nog steeds werd gebruikt tijdens de contrareformatie. Paus Gregorius I (ca. 540-604) is afgebeeld, de H. Mis opdragend, terwijl Christus als de Man van Smarten verschijnt op het altaar dat voor Sint Gregorius staat. Volgens de legende had St. Gregorius gebeden om een teken voor een betwijfelaar van de transsubstantiatieleer, waarop de lijdende Christus tijdens het opdragen van de Mis verscheen om hem te overtuigen en waarbij zijn bloed in de altaarkelk liep. Vaak zijn ook de passiewerktuigen afgebeeld. Zie de categorie Mass of Saint Gregory van Wikimedia Commons voor mediabestanden over dit onderwerp. This page is onl
Read more