A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Grid Drawings of Five-Connected Plane Graphs Desenhos de grade de gráficos planos de cinco conexões

Kazuyuki MIURA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Um desenho de grade de um gráfico plano G é um desenho de G no plano de modo que todos os vértices de G são colocados em pontos de grade plana e todas as arestas são desenhadas como segmentos de linha reta entre seus pontos finais, sem qualquer interseção de arestas. Neste artigo, fornecemos um algoritmo de tempo linear para encontrar um desenho de grade de qualquer grafo plano 5 conectado. G com cinco ou mais vértices na face externa. O tamanho do desenho satisfaz W + Hn - 2, onde n é o número de vértices em G, W é a largura e H é a altura do desenho da grade.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1228-1234
Data de publicação
2022/09/01
Publicitada
2022/02/16
ISSN online
1745-1337
DOI
10.1587/transfun.2021DMP0010
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria
Gráficos e Redes, Algoritmos e Estruturas de Dados

autores

Kazuyuki MIURA
  Fukushima University

Palavra-chave