Duplos de triangulação únicos de polígonos simples

Dada uma triangulação (sem pontos de Steiner) de um polígono simples , pode-se considerar o duplo dessa triangulação, que é definido da seguinte forma. Criamos um vértice para cada triângulo em nossa triangulação e conectamos dois vértices se os triângulos correspondentes compartilharem uma aresta. O gráfico duplo é conhecido por ser uma árvore com grau máximo de três.$P$

Para minha inscrição, estou interessado no seguinte. Dada uma árvore com o máximo grau três, há sempre um polígono simples P tal que o dual de cada triangulação (sem pontos de Steiner) de P é igual a T . Aqui, a triangulação de P pode não ser única, mas eu exijo que o gráfico duplo seja único.$T$$P$$P$$T$$P$

Isso certamente é verdade quando é um caminho, mas fica claro quando você tem vértices de grau três.$T$

Dada uma árvore com grau máximo três, sempre existe um polígono simples P, de modo que o duplo de toda triangulação (sem pontos de Steiner) de P seja igual a T ?$T$$P$$P$$T$

Sim. Para mostrar isso, darei um procedimento para obter o resultado aparentemente um pouco mais forte *:

Dada uma árvore com grau máximo três, construa um polígono simples P , de modo que a triangulação única de P (sem pontos de Steiner) tenha T como seu duplo.$T$$P$$P$$T$

Comece criando um triângulo inicial , representando algum vértice v 0 em T e adicione v 0 à fila$\Delta_0$$v_0$$T$$v_0$ . Em seguida, repita o seguinte até Q ficar vazio:$Q$$Q$

• Retire o elemento superior, , da fila.$v$
• Para cada vértice vizinha que para os quais não têm colocado um triângulo ainda, escolher um lado Um B de triângulo Δ v e um ponto D no interior das regiões cónicas gerados pela linha através de um B e seus segmentos vizinhos, de tal modo que o triângulo Δ A B D não cruza nenhum outro triângulo. (Ver figura abaixo) Conjunto Δ w ← Δ A B D e adicionar W para Q .$w$$AB$$\Delta_v$$D$$AB$$\Delta ABD$$\Delta_w\leftarrow\Delta ABD$$w$$Q$

Esta imagem fornece um exemplo de um possível polígono (esquerda) para o dado T (direita)$P$$T$

$AB$$AD$

$CD$$P$$Q \notin \{B,D\}$$DQ$$P$$AD$$BD$$\Delta ABD$$Q$existe apenas se existir um ponto análogo para o triângulo colocado anteriormente. Como não existe esse ponto para o primeiro triângulo, isso significa que não existe um ponto para qualquer triângulo que adicionarmos.

$(X,Y)$$P$$XY$$P$$P$

Observe que os polígonos construídos neste método tendem a ter ângulos bastante agudos. Suspeito que grandes gráficos arbitrários exijam polígonos com pequenos ângulos arbitrários, o que pode ser um problema ao desenhar esses polígonos com precisão finita.

_{*: A diferença é que, se interpretarmos 'único' como isomorfismo (que é consistente com a singularidade de triangulações e duais serem diferentes), estaríamos bem com um polígono com múltiplas triangulações e todos com duais isomórficos. No entanto, é possível 'anexar' mais triângulos a esses polígonos para garantir que alguns duplos não sejam mais isomórficos.}