Gráfico plano - Planar graph

Gráficos de exemplo
Planar	Não planar
Gráfico de borboleta	Gráfico completo K ₅
Gráfico completo K ₄	Gráfico de utilidade K _3,3

Na teoria dos grafos , um grafo plano é um grafo que pode ser embutido no plano , ou seja, pode ser desenhado no plano de tal forma que suas arestas se cruzem apenas em seus pontos finais. Em outras palavras, ele pode ser desenhado de forma que nenhuma aresta se cruze. Esse desenho é chamado de gráfico plano ou incorporação planar do gráfico . Um gráfico plano pode ser definido como um gráfico plano com um mapeamento de cada nó a um ponto em um plano, e de cada aresta a uma curva plana naquele plano, de modo que os pontos extremos de cada curva são os pontos mapeados a partir de seu final nós, e todas as curvas são disjuntas, exceto em seus pontos extremos.

Todo gráfico que pode ser desenhado em um plano pode ser desenhado também na esfera , e vice-versa, por meio de projeção estereográfica .

Os gráficos planos podem ser codificados por mapas combinatórios ou sistemas de rotação .

Uma classe de equivalência de desenhos topologicamente equivalentes na esfera, geralmente com suposições adicionais, como a ausência de istmos , é chamada de mapa planar . Embora um gráfico plano tenha uma face externa ou ilimitada , nenhuma das faces de um mapa planar tem um status específico.

Grafos planos generalizam para gráficos desenhados em uma superfície de um determinado gênero . Nesta terminologia, os grafos planares têm gênero 0, já que o plano (e a esfera) são superfícies do gênero 0. Consulte " incorporação de grafos " para outros tópicos relacionados.

Teoremas de Kuratowski e Wagner

Prova sem palavras de que o gráfico de tesserato não é plano usando os teoremas de Kuratowski ou Wagner e encontrando os subgráficos K ₅ (topo) ou K _3,3 (fundo)

O matemático polonês Kazimierz Kuratowski forneceu uma caracterização de grafos planares em termos de grafos proibidos , agora conhecido como teorema de Kuratowski :

Um grafo finito é plano se e somente se não contém um subgrafo que é uma subdivisão do grafo completo K ₅ ou do grafo bipartido completo ( grafo utilitário ).

K_{3,3}

Uma subdivisão de um gráfico resulta da inserção de vértices nas arestas (por exemplo, alterando uma aresta • —— • para • - • - •) zero ou mais vezes.

Um exemplo de gráfico sem subgrafo K ₅ ou K _3,3 . No entanto, ele contém uma subdivisão de K _3,3 e, portanto, não é plano.

Em vez de considerar subdivisões, o teorema de Wagner lida com menores :

Um grafo finito é plano se e somente se não tem ou como menor .

K_{5}

K_{3,3}

Um menor de um gráfico resulta de pegar um subgrafo e contrair repetidamente uma aresta em um vértice, com cada vizinho dos vértices finais originais se tornando um vizinho do novo vértice.

Uma animação mostrando que o gráfico de Petersen contém um menor isomórfico ao gráfico K _3,3 e, portanto, não é plano

Klaus Wagner perguntou de forma mais geral se qualquer classe de gráficos menor-fechada é determinada por um conjunto finito de " menores proibidos ". Este é agora o teorema de Robertson-Seymour , provado em uma longa série de artigos. Na linguagem deste teorema, e são os menores proibidos para a classe de grafos planares finitos. $K_{5}$ $K_{3,3}$

Outros critérios de planaridade

Na prática, é difícil usar o critério de Kuratowski para decidir rapidamente se um dado gráfico é plano. Porém, existem algoritmos rápidos para este problema: para um grafo com n vértices, é possível determinar no tempo O ( n ) (tempo linear) se o grafo pode ser plano ou não (ver teste de planaridade ).

Para um simples, ligado, gráfico planar com v vértices e e arestas e f caras, as seguintes condições simples para segurar v ≥ 3:

Teorema 1. e ≤ 3 v - 6;
Teorema 2. Se não houver ciclos de comprimento 3, então e ≤ 2 v - 4.
Teorema 3. f ≤ 2 v - 4.

Nesse sentido, grafos planos são grafos esparsos , pois possuem apenas O ( v ) arestas, assintoticamente menores que o máximo O ( v ² ). O grafo K _3,3 , por exemplo, possui 6 vértices, 9 arestas e nenhum ciclo de comprimento 3. Portanto, pelo Teorema 2, ele não pode ser plano. Esses teoremas fornecem condições necessárias para a planaridade que não são condições suficientes e, portanto, só podem ser usados para provar que um gráfico não é plano, nem que seja plano. Se ambos os teoremas 1 e 2 falharem, outros métodos podem ser usados.

O critério de planaridade de Whitney fornece uma caracterização baseada na existência de um dual algébrico;
O critério de planaridade de Mac Lane fornece uma caracterização algébrica de grafos planares finitos, por meio de seus espaços de ciclo ;
O critério de planaridade Fraysseix – Rosenstiehl fornece uma caracterização baseada na existência de uma bipartição das arestas do cotree de uma árvore de busca em profundidade. É fundamental para o algoritmo de teste de planaridade esquerda-direita ;
O teorema de Schnyder fornece uma caracterização da planaridade em termos de dimensão de ordem parcial ;
O critério de planaridade de Colin de Verdière fornece uma caracterização baseada na multiplicidade máxima do segundo autovalor de certos operadores de Schrödinger definidos pelo gráfico.
O teorema de Hanani-Tutte afirma que um gráfico é plano se e somente se ele tem um desenho no qual cada par independente de arestas cruza um número par de vezes; ele pode ser usado para caracterizar os gráficos planares por meio de um sistema de equações módulo 2.

Fórmula de Euler

A fórmula de Euler afirma que se um gráfico finito, conectado e planar é desenhado no plano sem nenhuma interseção de arestas, ev é o número de vértices, e é o número de arestas ef é o número de faces (regiões delimitadas por arestas, incluindo a região externa infinitamente grande), então

v-e+f=2.

Como ilustração, no gráfico de borboleta dado acima, v = 5, e = 6 e f = 3. Em geral, se a propriedade for válida para todos os gráficos planares de faces f , qualquer alteração no gráfico que cria uma face adicional, mantendo o gráfico planar manteria v - e + f invariante. Uma vez que a propriedade é válida para todos os gráficos com f = 2, por indução matemática ela é válida para todos os casos. A fórmula de Euler também pode ser provada da seguinte forma: se o gráfico não é uma árvore , remova uma aresta que completa um ciclo . Isso diminui e e f em um, deixando v - e + f constante. Repita até que o gráfico restante seja uma árvore; árvores têm v = e + 1 ef = 1, resultando em v - e + f = 2, ou seja, a característica de Euler é 2.

Em um grafo finito, conectado , simples e planar, qualquer face (exceto possivelmente a externa) é limitada por pelo menos três arestas e cada aresta toca no máximo duas faces; usando a fórmula de Euler, pode-se, em seguida, mostram que estes gráficos são escassas no sentido em que se v ≥ 3:

e\leq 3v-6.

Um diagrama de Schlegel de um dodecaedro regular , formando um gráfico planar de um poliedro convexo.

A fórmula de Euler também é válida para poliedros convexos . Isso não é coincidência: cada poliedro convexo pode ser transformado em um gráfico planar simples conectado usando o diagrama de Schlegel do poliedro, uma projeção em perspectiva do poliedro em um plano com o centro da perspectiva escolhido próximo ao centro de um dos faces do poliedro. Nem todo grafo planar corresponde a um poliedro convexo dessa forma: as árvores não, por exemplo. O teorema de Steinitz diz que os grafos poliédricos formados a partir de poliedros convexos são precisamente os grafos planares simples 3-conectados finitos. De maneira mais geral, a fórmula de Euler se aplica a qualquer poliedro cujas faces são polígonos simples que formam uma superfície topologicamente equivalente a uma esfera, independentemente de sua convexidade.

Grau médio

Gráficos planares conectados com mais de uma aresta obedecem à desigualdade , porque cada face tem pelo menos três incidências de aresta e cada aresta contribui com exatamente duas incidências. Segue por meio de transformações algébricas dessa desigualdade com a fórmula de Euler que, para gráficos planares finitos, o grau médio é estritamente menor que 6. Os gráficos com grau médio mais alto não podem ser planos. $2e\geq 3f$ $v-e+f=2$

Gráficos de moedas

Exemplo do teorema de empacotamento de círculo em K ^-₅ , o gráfico completo em cinco vértices, menos uma aresta.

Dizemos que dois círculos desenhados em um plano se beijam (ou osculam ) sempre que se cruzam em exatamente um ponto. Um "gráfico de moeda" é um gráfico formado por um conjunto de círculos, nenhum dos quais com interiores sobrepostos, formando um vértice para cada círculo e uma aresta para cada par de círculos que se beijam. O teorema de empacotamento de círculos , provado pela primeira vez por Paul Koebe em 1936, afirma que um gráfico é plano se e somente se for um gráfico de moeda.

Esse resultado fornece uma prova fácil do teorema de Fáry , de que todo grafo planar simples pode ser embutido no plano de forma que suas arestas sejam segmentos de linha reta que não se cruzam. Se colocarmos cada vértice do gráfico no centro do círculo correspondente em uma representação gráfica de moeda, os segmentos de linha entre os centros dos círculos que se beijam não cruzam nenhuma das outras arestas.

Densidade do gráfico planar

A densidade de um grafo planar, ou rede, é definida como uma razão entre o número de arestas e o número de arestas possíveis em uma rede com nós, dada por um grafo plano , dando . Um grafo planar completamente esparso tem , alternativamente, um grafo planar completamente denso tem $D$ $E$ $N$ $(E_{\max }=3N-6)$ $D={\frac {E-N+1}{2N-5}}$ $D=0$ $D=1$

Famílias de gráficos relacionados

Gráficos planares máximos

O gráfico de Goldner-Harary é planar máximo. Todas as suas faces são delimitadas por três arestas.

Um gráfico simples é chamado de plano máximo se for plano, mas adicionar qualquer aresta (no conjunto de vértices fornecido) destruiria essa propriedade. Todas as faces (incluindo a externa) são então delimitadas por três arestas, explicando o termo alternativo triangulação plana . Os nomes alternativos "gráfico triangular" ou "gráfico triangulado" também têm sido usados, mas são ambíguos, visto que mais comumente se referem ao gráfico de linha de um gráfico completo e aos gráficos de cordas, respectivamente. Cada gráfico planar máximo é pelo menos 3-conectado.

Se um grafo planar máximo tem v vértices com v > 2, então ele tem precisamente 3 v - 6 arestas e 2 v - 4 faces.

As redes apolíneas são os gráficos planares máximos formados pela divisão repetida de faces triangulares em triplos de triângulos menores. Equivalentemente, eles são as 3 árvores planas .

Os gráficos estrangulados são os gráficos em que cada ciclo periférico é um triângulo. Em um gráfico plano máximo (ou mais geralmente um gráfico poliédrico), os ciclos periféricos são as faces, portanto, os gráficos planos máximos são estrangulados. Os grafos estrangulados incluem também os grafos cordais , e são exatamente os grafos que podem ser formados por somas clique (sem deletar arestas) de grafos completos e grafos planares máximos.

Gráficos externos planares

Grafos externos planares são gráficos com um embedding no plano de forma que todos os vértices pertençam à face ilimitada do embedding. Todo grafo do plano externo é plano, mas o inverso não é verdadeiro: K ₄ é plano, mas não plano externo. Um teorema semelhante ao de Kuratowski afirma que um grafo finito é planar externo se e somente se ele não contém uma subdivisão de K ₄ ou de K _2,3 . O exposto acima é um corolário direto do fato de que um grafo G é planar externo se o grafo formado a partir de G pela adição de um novo vértice, com arestas conectando-o a todos os outros vértices, for um grafo plano.

Uma incorporação de plano externo 1 de um gráfico é o mesmo que uma incorporação de plano externo. Para k > 1, um embedding plano é k -outerplanar se a remoção dos vértices na face externa resultar em um embedding ( k - 1) -outerplanar. Um gráfico é k -outerplanar se tiver uma incorporação k -outerplanar.

Gráficos Halin

Um grafo Halin é um grafo formado a partir de uma árvore plana não direcionada (sem nós de grau dois) conectando suas folhas em um ciclo, na ordem dada pela incorporação plana da árvore. Equivalentemente, é um gráfico poliédrico em que uma face é adjacente a todas as outras. Cada gráfico Halin é plano. Assim como os grafos externos planares, os grafos Halin possuem baixa largura de árvore , tornando muitos problemas algorítmicos neles mais facilmente resolvidos do que em grafos planares irrestritos.

Outras famílias relacionadas

Um grafo de vértice é um grafo que pode ser tornado plano pela remoção de um vértice, e um grafo k -apex é um grafo que pode se tornar plano pela remoção de no máximo k vértices.

Um gráfico 1-planar é um gráfico que pode ser desenhado no plano com no máximo um cruzamento simples por aresta, e um gráfico k -planar é um gráfico que pode ser desenhado com no máximo k cruzamentos simples por aresta.

Um gráfico de mapa é um gráfico formado a partir de um conjunto de regiões disjuntas interiores finitamente conectadas e simplesmente conectadas no plano, conectando duas regiões quando elas compartilham pelo menos um ponto limite. Quando no máximo três regiões se encontram em um ponto, o resultado é um gráfico planar, mas quando quatro ou mais regiões se encontram em um ponto, o resultado pode ser não-plano.

Um gráfico toroidal é um gráfico que pode ser incorporado sem cruzamentos no toro . Mais geralmente, o gênero de um gráfico é o gênero mínimo de uma superfície bidimensional na qual o gráfico pode ser incorporado; gráficos planares têm gênero zero e gráficos toroidais não planares têm gênero um.

Qualquer gráfico pode ser incorporado no espaço tridimensional sem cruzamentos. No entanto, um análogo tridimensional dos gráficos planares é fornecido pelos gráficos embutidos sem links , gráficos que podem ser embutidos no espaço tridimensional de tal forma que não há dois ciclos topologicamente vinculados um ao outro. Em analogia às caracterizações de Kuratowski e Wagner dos gráficos planares como sendo os gráficos que não contêm K ₅ ou K _3,3 como menor, os gráficos incorporáveis sem ligações podem ser caracterizados como os gráficos que não contêm como menor qualquer um dos sete gráficos na família Petersen . Em analogia às caracterizações dos grafos planares externos e planares como sendo os grafos com invariante de grafo de Colin de Verdière no máximo dois ou três, os grafos embutidos sem ligações são os gráficos que têm invariante de Colin de Verdière no máximo quatro.

Um grafo planar ascendente é um grafo acíclico direcionado que pode ser desenhado no plano com suas arestas como curvas não cruzadas que são consistentemente orientadas em uma direção ascendente. Nem todo grafo acíclico dirigido por planar é planar ascendente e é NP-completo para testar se um dado grafo é planar ascendente.

Enumeração de gráficos planares

A assintótica para o número de gráficos planares (rotulados) nos vértices é , onde e . $n$ $g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!$ $\gamma \approx 27.22687$ $g\approx 0.43\times 10^{-5}$

Quase todos os gráficos planares têm um número exponencial de automorfismos.

O número de gráficos planares não rotulados (não isomórficos) nos vértices está entre e . $n$ $27.2^{n}$ $30.06^{n}$

Outros fatos e definições

Os quatro cor teorema estados que cada gráfico planar é a 4- colorível (ou seja, 4-partite).

O teorema de Fáry afirma que todo grafo planar simples admite um embedding no plano de tal forma que todas as arestas são segmentos de linha reta que não se cruzam. Um conjunto de pontos universal é um conjunto de pontos tal que todo grafo planar com n vértices possui tal incorporação com todos os vértices no conjunto de pontos; existem conjuntos de pontos universais de tamanho quadrático, formados tomando um subconjunto retangular da rede inteira . Todo grafo plano externo simples admite uma incorporação no plano de modo que todos os vértices fiquem em um círculo fixo e todas as arestas são segmentos de linha reta que ficam dentro do disco e não se cruzam, então polígonos regulares de n- vértices são universais para grafos planares externos.

Um gráfico planar e seu dual

Dado um G embutido de um gráfico conectado (não necessariamente simples) no plano sem interseções de aresta, construímos o grafo dual G * da seguinte forma: escolhemos um vértice em cada face de G (incluindo a face externa) e para cada aresta e em G , introduzimos uma nova aresta em G * conectando os dois vértices em G * correspondentes às duas faces em G que se encontram em e . Além disso, essa aresta é desenhada de modo que cruze e exatamente uma vez e que nenhuma outra aresta de G ou G * seja interceptada. Então G * é novamente a incorporação de um grafo planar (não necessariamente simples); ele tem tantas arestas quanto G , tantos vértices quanto G tem faces e tantas faces quanto G tem vértices. O termo "dual" é justificado pelo fato de que G ** = G ; aqui a igualdade é a equivalência dos encaixes na esfera . Se G é o gráfico planar correspondente a um poliedro convexo, então G * é o gráfico planar correspondente ao poliedro dual.

Os duais são úteis porque muitas propriedades do gráfico duplo estão relacionadas de maneiras simples às propriedades do gráfico original, permitindo que os resultados sejam comprovados sobre os gráficos examinando seus gráficos duais.

Enquanto o dual construído para um embedding particular é único (até isomorfismo ), os gráficos podem ter duais diferentes (isto é, não isomórficos), obtidos de embeddings diferentes (isto é, não homeomórficos ).

Um gráfico euclidiano é um gráfico no qual os vértices representam pontos no plano, e as arestas recebem comprimentos iguais à distância euclidiana entre esses pontos; veja a teoria dos grafos geométricos .

Um gráfico plano é considerado convexo se todas as suas faces (incluindo a face externa) forem polígonos convexos . Um gráfico plano pode ser desenhado convexamente se, e somente se, for uma subdivisão de um gráfico plano conectado a 3 vértices .

A conjectura de Scheinerman (agora um teorema) afirma que todo gráfico planar pode ser representado como um gráfico de interseção de segmentos de linha no plano.

O teorema do separador planar afirma que todo grafo planar de n- vértices pode ser particionado em dois subgráficos de tamanho no máximo 2 n / 3 pela remoção de O ( √ n ) vértices. Como consequência, os gráficos planares também têm largura da árvore e largura do ramo O ( √ n ).

O teorema da estrutura do produto planar afirma que todo gráfico planar é um subgráfico do produto gráfico forte de um gráfico de largura de árvore no máximo 8 e um caminho. Este resultado foi usado para mostrar que os gráficos planares possuem um número de fila limitado , um número cromático não repetitivo limitado e gráficos universais de tamanho quase linear. Ele também tem aplicações para classificação de vértices e coloração centrada em p de gráficos planares.

Para dois grafos planares com v vértices, é possível determinar no tempo O ( v ) se eles são isomórficos ou não (veja também o problema de isomorfismo de grafos ).

O coeficiente de malha de um gráfico planar normaliza seu número de faces limitadas (o mesmo que a classificação do circuito do gráfico, pelo critério de planaridade de Mac Lane ) dividindo-o por 2 n - 5, o número máximo possível de faces limitadas em um gráfico planar com n vértices. Portanto, varia de 0 para árvores a 1 para gráficos planares máximos.

Os gráficos planares representáveis por palavras incluem gráficos planares sem triângulo e, mais geralmente, gráficos planares com três cores, bem como certas subdivisões de faces de gráficos de grade triangular e certas triangulações de gráficos de cilindro cobertos por grade.

Veja também

Mapa combinatório - um objeto combinatório que pode codificar gráficos planos
Planarização , um grafo planar formado a partir de um desenho com cruzamentos, substituindo cada ponto de cruzamento por um novo vértice
Espessura (teoria dos grafos) , o menor número de grafos planares em que as arestas de um dado gráfico podem ser particionadas
Planarity , um jogo de quebra-cabeça de computador em que o objetivo é embutir um gráfico planar em um plano
Sprouts (jogo) , um jogo de lápis e papel em que um gráfico plano sujeito a certas restrições é construído como parte do jogo
Problema de três utilitários , um quebra-cabeça popular

Notas

^ Trudeau, Richard J. (1993). Introdução à teoria de grafos (republicação corrigida e ampliada. Ed.). Nova York: Dover Pub. p. 64. ISBN 978-0-486-67870-2. Retirado em 8 de agosto de 2012 . Assim, um gráfico plano, quando desenhado em uma superfície plana, não tem cruzamentos de arestas ou pode ser redesenhado sem eles.
^ Barthelemy, M. (2017). Morfogênese de Redes Espaciais . Nova York: Springer. p. 6
^ Schnyder, W. (1989), "Planar graphs and poset dimension", Order , 5 (4): 323-343, doi : 10.1007 / BF00353652 , MR 1010382 , S2CID 122785359.
^ Bhasker, Jayaram; Sahni, Sartaj (1988), "Um algoritmo linear para encontrar um dual retangular de um gráfico triangulado planar", Algorithmica , 3 (1-4): 247-278, doi : 10.1007 / BF01762117 , S2CID 2709057.
^ Seymour, PD; Weaver, RW (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241-251, doi : 10.1002 / jgt.3190080206 , MR 0742878.
^ Felsner, Stefan (2004), "1.4 Outerplanar Graphs and Convex Geometric Graphs", Grafos e arranjos geométricos , Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Wiesbaden, pp. 6–7, doi : 10.1007 / 978-3-322-80303-0_1 , ISBN 3-528-06972-4, MR 2061507
^ Sysło, Maciej M .; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference realizada em Lagów, Polônia, de 10 a 13 de fevereiro de 1981 , Lecture Notes in Mathematics, 1018 , Springer-Verlag, pp. 248-256, doi : 10.1007 / BFb0071635.
^ Giménez, Omer; Noy, Marc (2009). "Enumeração assintótica e leis de limite de grafos planares". Journal of the American Mathematical Society . 22 (2): 309–329. arXiv : math / 0501269 . Bibcode : 2009JAMS ... 22..309G . doi : 10.1090 / s0894-0347-08-00624-3 . S2CID 3353537 .
^ McDiarmid, Colin; Steger, Angelika ; Welsh, Dominic JA (2005). "Gráficos planares aleatórios". Journal of Teoria Combinatória, Série B . 93 (2): 187–205. CiteSeerX 10.1.1.572.857 . doi : 10.1016 / j.jctb.2004.09.007 .
^ Bonichon, N .; Gavoille, C .; Hanusse, N .; Poulalhon, D .; Schaeffer, G. (2006). "Gráficos Planares, via Mapas e Árvores Bem Ordenados". Gráficos e Combinatória . 22 (2): 185–202. CiteSeerX 10.1.1.106.7456 . doi : 10.1007 / s00373-006-0647-2 . S2CID 22639942 .
^ Dujmović, Vida ; Joret, Gwenäel; Micek, Piotr; Morin, Pat ; Ueckerdt, Torsten; Wood, David R. (2020), "Planar graphs have bounded queue number", Journal of the ACM , 67 (4): 22: 1-22: 38, arXiv : 1904.04791 , doi : 10.1145 / 3385731
^ Bose, Prosenjit; Dujmović, Vida ; Javarsineh, Mehrnoosh; Morin, Pat (2020), classificação de vértices assintoticamente ótima de gráficos planares , arXiv : 2007.06455
^ Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2019), Improved bounds for centered colorings , arXiv : 1907.04586
^ É Filotti, Jack N. Mayer. Um algoritmo de tempo polinomial para determinar o isomorfismo de grafos de gênero fixo. Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236–243. 1980.
^ Buhl, J .; Gautrais, J .; Sole, RV; Kuntz, P .; Valverde, S .; Deneubourg, JL; Theraulaz, G. (2004), "Eficiência e robustez em redes de formigas de galerias", European Physical Journal B , Springer-Verlag, 42 (1): 123–129, Bibcode : 2004EPJB ... 42..123B , doi : 10,1140 / epjb / e2004-00364-9 , S2CID 14975826.
^ M. Halldórsson, S. Kitaev e A. Pyatkin. Orientações semitransitivas e gráficos representáveis por palavras, Discr. Appl. Matemática. 201 (2016), 164-171.
^ TZQ Chen, S. Kitaev, e BY Sun. Representabilidade de palavra de subdivisões de face de gráficos de grade triangular, gráficos e combinação. 32 (5) (2016), 1749-1761.
^ TZQ Chen, S. Kitaev, e BY Sun. Representabilidade de palavras de triangulações de gráficos cilíndricos cobertos por grade, Discr. Appl. Matemática. 213 (2016), 60-70.

Referências

Kuratowski, Kazimierz (1930), "Sur le problems des courbes gauches en topologie" (PDF) , Fundamenta Mathematicae (em francês), 15 : 271-283, doi : 10.4064 / fm-15-1-271-283.
Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen (em alemão), 114 : 570-590, doi : 10.1007 / BF01594196 , S2CID 123534907.
Boyer, John M .; Myrvold, Wendy J. (2005), "Na vanguarda: planaridade O (n) simplificado por adição de aresta" (PDF) , Journal of Graph Algorithms and Applications , 8 (3): 241-273, doi : 10.7155 / jgaa 0,00091.
McKay, Brendan ; Brinkmann, Gunnar, um gerador de gráfico planar útil.
de Fraysseix, H .; Ossona de Mendez, P .; Rosenstiehl, P. (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science , 17 (5): 1017–1029, arXiv : math / 0610935 , doi : 10.1142 / S0129054106004248 , S2CID 40107560. Edição especial sobre desenho gráfico.
DA Bader e S. Sreshta, A New Parallel Algorithm for Planarity Testing , UNM-ECE Technical Report 03-002, 1 de outubro de 2003.
Fisk, Steve (1978), "Uma curta prova do teorema do vigia de Chvátal", Journal of Combinatorial Theory, Series B , 24 (3): 374, doi : 10.1016 / 0095-8956 (78) 90059-X.

links externos

Código-fonte do algoritmo de planaridade de adição de borda, versão 1.0 - código-fonte C grátis para implementação de referência do algoritmo de planaridade de Boyer-Myrvold, que fornece um embedder planar combinatório e isolador de subgrafo Kuratowski. Um projeto de código aberto com licenciamento gratuito fornece os Algoritmos de Planaridade de Adição de Borda, versão atual .
Implementação pública de um algoritmo Biblioteca Graph and Editor - GPL biblioteca algoritmo gráfico incluindo testes planaridade, embedder planaridade e Kuratowski exposição subgráfico em tempo linear.
Boost Graph Library tools para gráficos planares , incluindo teste de planaridade de tempo linear, incorporação, isolamento de subgrafo de Kuratowski e desenho em linha reta.
3 Utilities Puzzle e Planar Graphs
Modelo de planaridade NetLogo - versão NetLogo do jogo de John Tantalo

[1] Trudeau, Richard J. (1993). Introdução à teoria de grafos (republicação corrigida e ampliada. Ed.). Nova York: Dover Pub. p. 64. ISBN 978-0-486-67870-2. Retirado em 8 de agosto de 2012 . Assim, um gráfico plano, quando desenhado em uma superfície plana, não tem cruzamentos de arestas ou pode ser redesenhado sem eles.

[2] Barthelemy, M. (2017). Morfogênese de Redes Espaciais . Nova York: Springer. p. 6

[3] Schnyder, W. (1989), "Planar graphs and poset dimension", Order , 5 (4): 323-343, doi : 10.1007 / BF00353652 , MR 1010382 , S2CID 122785359.

[4] Bhasker, Jayaram; Sahni, Sartaj (1988), "Um algoritmo linear para encontrar um dual retangular de um gráfico triangulado planar", Algorithmica , 3 (1-4): 247-278, doi : 10.1007 / BF01762117 , S2CID 2709057.

[5] Seymour, PD; Weaver, RW (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241-251, doi : 10.1002 / jgt.3190080206 , MR 0742878.

[6] Felsner, Stefan (2004), "1.4 Outerplanar Graphs and Convex Geometric Graphs", Grafos e arranjos geométricos , Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Wiesbaden, pp. 6–7, doi : 10.1007 / 978-3-322-80303-0_1 , ISBN 3-528-06972-4, MR 2061507

[7] Sysło, Maciej M .; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference realizada em Lagów, Polônia, de 10 a 13 de fevereiro de 1981 , Lecture Notes in Mathematics, 1018 , Springer-Verlag, pp. 248-256, doi : 10.1007 / BFb0071635.

[8] Giménez, Omer; Noy, Marc (2009). "Enumeração assintótica e leis de limite de grafos planares". Journal of the American Mathematical Society . 22 (2): 309–329. arXiv : math / 0501269 . Bibcode : 2009JAMS ... 22..309G . doi : 10.1090 / s0894-0347-08-00624-3 . S2CID 3353537 .

[9] McDiarmid, Colin; Steger, Angelika ; Welsh, Dominic JA (2005). "Gráficos planares aleatórios". Journal of Teoria Combinatória, Série B . 93 (2): 187–205. CiteSeerX 10.1.1.572.857 . doi : 10.1016 / j.jctb.2004.09.007 .

[10] Bonichon, N .; Gavoille, C .; Hanusse, N .; Poulalhon, D .; Schaeffer, G. (2006). "Gráficos Planares, via Mapas e Árvores Bem Ordenados". Gráficos e Combinatória . 22 (2): 185–202. CiteSeerX 10.1.1.106.7456 . doi : 10.1007 / s00373-006-0647-2 . S2CID 22639942 .

[11] Dujmović, Vida ; Joret, Gwenäel; Micek, Piotr; Morin, Pat ; Ueckerdt, Torsten; Wood, David R. (2020), "Planar graphs have bounded queue number", Journal of the ACM , 67 (4): 22: 1-22: 38, arXiv : 1904.04791 , doi : 10.1145 / 3385731

[12] Bose, Prosenjit; Dujmović, Vida ; Javarsineh, Mehrnoosh; Morin, Pat (2020), classificação de vértices assintoticamente ótima de gráficos planares , arXiv : 2007.06455

[13] Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2019), Improved bounds for centered colorings , arXiv : 1907.04586

[14] É Filotti, Jack N. Mayer. Um algoritmo de tempo polinomial para determinar o isomorfismo de grafos de gênero fixo. Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236–243. 1980.

[15] Buhl, J .; Gautrais, J .; Sole, RV; Kuntz, P .; Valverde, S .; Deneubourg, JL; Theraulaz, G. (2004), "Eficiência e robustez em redes de formigas de galerias", European Physical Journal B , Springer-Verlag, 42 (1): 123–129, Bibcode : 2004EPJB ... 42..123B , doi : 10,1140 / epjb / e2004-00364-9 , S2CID 14975826.

[HKP16-16] M. Halldórsson, S. Kitaev e A. Pyatkin. Orientações semitransitivas e gráficos representáveis por palavras, Discr. Appl. Matemática. 201 (2016), 164-171.

[CKS2016-17] TZQ Chen, S. Kitaev, e BY Sun. Representabilidade de palavra de subdivisões de face de gráficos de grade triangular, gráficos e combinação. 32 (5) (2016), 1749-1761.

[CKS2016-2-18] TZQ Chen, S. Kitaev, e BY Sun. Representabilidade de palavras de triangulações de gráficos cilíndricos cobertos por grade, Discr. Appl. Matemática. 213 (2016), 60-70.

Languages

In other projects