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

Trade off between Page Number and Number of Edge-Crossings on the Spine of Book Embeddings of Graphs Troca entre o número da página e o número de cruzamentos de bordas na lombada do livro Incorporações de gráficos

Miki Shimabara MIYAUCHI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Este artigo estuda o problema de incorporações de livros de gráficos. Quando cada aresta pode aparecer em uma ou mais páginas cruzando a lombada de um livro, é sabido que todo gráfico G pode ser incorporado em um livro de 3 páginas. Recentemente, foi demonstrado que existe um livro de 3 páginas incorporado de G em que cada borda cruza a lombada O(registro2 n) vezes. Este artigo considera um livro com mais de três páginas. Neste caso, sabe-se que um gráfico completo Kn fazendo o melhor dos nossos n vértices podem ser incorporados em um n/2 Livro de páginas sem cruzamentos nas bordas da lombada. Assim, torna-se um problema interessante conceber incorporações de livros de G de modo a reduzir o número de páginas utilizadas e o número de cruzamentos de bordas na lombada. Este artigo mostra que existe uma dincorporação de livro de páginas de G em que cada borda cruza a lombada O(registrod n) vezes. Como corolário direto, para qualquer número real s, há um ns incorporação de livro de páginas de G em que cada aresta cruza a lombada um número constante de vezes. Em outro artigo, Enomoto-Miyauchi-Ota mostram que para um número inteiro d, Se n é suficientemente grande em comparação com d, então para qualquer incorporação de Kn em uma d-página do livro, deve existir Ω(n2 logd n) pontos nos quais as bordas cruzam a lombada. Isso significa que nosso resultado é o melhor possível para Kn nesse caso.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.8 pp.1732-1734
Data de publicação
2000/08/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
LETTER
Categoria
Gráficos e Redes

autores

Palavra-chave