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

An Exact Algorithm for the Arrow Placement Problem in Directed Graph Drawings Um algoritmo exato para o problema de posicionamento de setas em desenhos de gráficos direcionados

Naoto KIDO, Sumio MASUDA, Kazuaki YAMAGUCHI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Consideramos o problema de colocar setas, que indicam a direção de cada aresta em desenhos de grafos direcionados, sem fazê-las se sobreporem tanto quanto possível a outras setas, vértices e arestas. Os dois métodos a seguir foram propostos para este problema. Trata-se de um algoritmo exato para o caso em que a posição de cada seta está restrita a alguns pontos discretos. O outro é um algoritmo heurístico para o caso em que a seta pode se mover continuamente em cada aresta. Neste artigo, assumimos que as posições das setas não estão restritas a pontos discretos e propomos um algoritmo exato para o problema de encontrar um posicionamento de setas tal que (a) a soma ponderada dos números de sobreposições com arestas, vértices e outras setas seja minimizada e (b) a soma das distâncias entre as setas e os vértices terminais de suas arestas é minimizada como objetivo secundário. O método proposto resolve este problema reduzindo-o a um problema de programação linear inteira mista. Como este é um algoritmo de tempo exponencial, adicionamos um procedimento simples como pré-processamento para reduzir o tempo de execução. Os resultados experimentais mostram que o método proposto pode encontrar um melhor posicionamento da seta do que os métodos anteriores e o procedimento para reduzir o tempo de execução é eficaz.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.11 pp.1481-1489
Data de publicação
2019/11/01
Publicitada
ISSN online
1745-1337
DOI
10.1587/transfun.E102.A.1481
Tipo de Manuscrito
PAPER
Categoria
Algoritmos e estruturas de dados

autores

Naoto KIDO
  Kobe University
Sumio MASUDA
  Kobe University
Kazuaki YAMAGUCHI
  Kobe University

Palavra-chave