Reduzindo Cruzamentos em Grafos Ordenados

Desenhar um gráfico no plano com o menor número de cruzamentos possível é um desafio chave na área de desenho de gráficos e geometria computacional. Uma abordagem para resolver isso é remover a menor quantidade de vértices ou arestas para que o gráfico restante possa ser desenhado sem cruzamentos. Esse artigo estuda ambos os problemas em um cenário onde a ordem dos vértices é fixa, conhecido como Gráfico Ordenado.

Nesse cenário, os vértices são colocados numa linha reta, chamada de espinha, e cada aresta que conecta os vértices deve ser desenhada em uma das várias páginas de um livro. O objetivo é garantir que cada aresta tenha um número limitado de cruzamentos. Em embaçamentos de livro, outra maneira de reduzir ou evitar cruzamentos é usando mais páginas. O número mínimo de páginas necessárias para desenhar um gráfico ordenado sem nenhum cruzamento é chamado de seu número de página.

Mostramos que o número de página de um gráfico ordenado com vértices e arestas pode ser computado em tempo. Uma aproximação desse número também pode ser encontrada de forma eficiente. Além disso, podemos determinar se é suficiente deletar arestas de um gráfico ordenado para conseguir um layout onde cada aresta cruza no máximo outras arestas em uma página. Um aspecto adicional deste estudo envolve o tamanho de um conjunto de interseção, que é um conjunto de pontos na espinha de modo que cada aresta contenha pelo menos um dos pontos.

Se houver um certo número de arestas a serem deletadas, podemos calcular o número mínimo de arestas cuja remoção resulta em um número de página de ordem fixa. Em certos casos, fornecemos um algoritmo em relação a alguns vértices que não estão na espinha. A ordem dos vértices na espinha é dada, e precisamos atribuir cada vértice que não está na espinha a uma das trilhas, que correspondem a linhas retas em uma página separada paralela à espinha. Nesse contexto, podemos minimizar ou o número de cruzamentos ou, se cruzamentos não forem permitidos, o número de trilhas.

Um número significativo de cruzamentos pode dificultar a interpretação do desenho de um gráfico. Assim, pesquisadores em desenho de gráficos buscam reduzir o número de cruzamentos. Vários aspectos desse problema foram examinados em termos de complexidade parametrizada. Por exemplo, existem algoritmos que podem decidir se um gráfico pode ser desenhado com um número limitado de cruzamentos.

Minimizar cruzamentos também foi estudado em casos onde cada vértice deve ser colocado em uma das duas linhas horizontais, o que é particularmente importante ao desenhar gráficos em camadas. Existem duas variantes dessa questão: uma onde os vértices em ambas as linhas podem ser arranjados livremente e outra onde a ordem dos vértices em uma linha é fixa. Ambas as variantes tiveram o desenvolvimento de algoritmos capazes de tratá-las.

Curiosamente, a minimização de cruzamentos continua a ser uma questão complicada mesmo quando restrita a gráficos que têm um subgráfico planar com apenas uma aresta a menos. Outra técnica para lidar com cruzamentos envolve remover alguns vértices ou arestas, permitindo que o gráfico restante seja desenhado sem cruzamentos. Notavelmente, foi estabelecido que deletar vértices para atingir a planaridade pode ser processado de forma eficiente em relação ao número de vértices removidos. No entanto, o tempo de execução desses algoritmos geralmente cresce significativamente com o número de vértices deletados.

Este estudo foca em outro modelo para abordar o problema de arestas cruzadas, ou seja, embaçamentos de livro. Nesses embaçamentos, os vértices do gráfico são organizados em uma linha reta chamada espinha, e as arestas devem ser desenhadas em páginas separadas de forma que o desenho de cada página seja livre de cruzamentos ou permita um certo número fixo de cruzamentos por aresta. A análise considera o cenário onde a ordem dos vértices é dada e permanece constante.

Descrevemos gráficos, denominados gráficos ordenados, consistindo em um conjunto de vértices juntamente com uma disposição ordenada desses vértices. Cada aresta conecta dois vértices nessa ordem fixa. Se duas arestas têm extremidades que se intersectam, sua representação como curvas também deve intersectar. Quando as arestas não se cruzam, como no caso de semicírculos, um desenho é alcançado onde as arestas cruzam apenas quando suas extremidades se entrelaçam.

Sob condições específicas, categorizamos um gráfico ordenado como -planar se cada aresta cruza no máximo outras arestas. Este artigo investiga particularmente algoritmos eficientes para remoção de arestas a fim de alcançar um layout planar.

A pesquisa também investiga um tipo de Gráfico de Conflito relacionado ao gráfico ordenado, representando arestas onde ocorrem cruzamentos. Pode ser visto como um gráfico circular, indicando as conexões entre as arestas com base em suas interseções. O problema é deletar um número limitado de vértices de modo que o gráfico restante atenda a certos critérios de grau.

O artigo conecta o número de página de ordem fixa de um gráfico com a colorabilidade de seu gráfico de conflito. É notado que determinar se o gráfico de conflito é bipartido é um passo chave. Além disso, outra abordagem envolve adicionar um ciclo que interliga vértices ao longo da espinha na ordem especificada, o que ajuda a testar a planaridade do gráfico.

Surpreendentemente, a questão da minimização de cruzamentos continua a ser NP-difícil mesmo quando restrita a tipos específicos de gráficos. Também há um foco no número mínimo de arestas ou vértices que podem ser removidos para que o gráfico restante possa ser desenhado sem cruzamentos.

Este trabalho investiga algoritmos parametrizados, onde os parâmetros podem incluir o número de arestas a serem deletadas, bem como o número de cruzamentos permitidos por aresta e como eles podem interagir.

No contexto de gráficos ordenados e suas propriedades, a pesquisa examina as condições sob as quais um gráfico pode ser desenhado sem cruzamentos, considerando a relação entre largura de árvore e o tamanho de separadores balanceados no gráfico de conflito.

Os autores fornecem uma estratégia para limitar a largura da árvore e destacam que gráficos planos ordenados possuem certas características de separador.

Para um gráfico ordenado, investigamos como o cruzamento de arestas afeta o desenho e quais implicações surgem quando arestas específicas devem ser removidas. A estratégia de ramificação utilizada leva a instâncias reduzidas que atendem a condições de cruzamento específicas.

Esclarecemos que gráficos ordenados com arranjos de arestas especificados podem ser simplificados através de soluções recursivas, que podem levar a layouts mais claros e compreensíveis. A existência de separadores balanceados no gráfico de conflito permite um processamento eficaz dessas instâncias.

Finalmente, o estudo discute vários problemas em aberto na área e considera se diferentes problemas de redução de cruzamento poderiam ser abordados com técnicas semelhantes. A análise da remoção de arestas para a outer-planaridade e as complexidades computacionais relacionadas é outra área para exploração futura.

No geral, essa pesquisa fornece uma visão abrangente das complexidades e estratégias envolvidas na redução de cruzamentos em gráficos ordenados, examinando tanto implicações teóricas quanto aplicações práticas em desenho de gráficos.