Skip to main content
deleted 185 characters in body
Source Link

This class is the same as the $\Delta$-confluent graphs introduced by Eppstein, Goodrich, and Meng (Delta-confluent Drawings). It is easy to see that $\Delta$-confluent graphs are closed under the operations you allow (and a single vertex is $\Delta$-confluent). On the other hand, a $C_5$ in a $\Delta$-confluent drawing must use aand all $\Delta$-junction, since the tree-confluent graphs are all bipartitecan be built using these operations (see Hui, Pelsmajer, Schaefer, Stefankovic, Train Tracks and Confluent Drawingseasy induction). But then there must be either two branches of the $\Delta$-junction each containing two vertices of the $C_5$ or one branch that contains three vertices of the $C_5$. In either case, the $C_5$ must have two disjoint chords.

Eppstein, Goodrich, and Meng also prove that the $\Delta$-confluent graphs are the same as the distance-hereditary graphs, so the result follows from that.

Theorem 2 in the Eppstein, Goodrich, and Meng paper is the result tying distance-heredity to the operations you allow. It's attributed to a 1986 paper by H. Bandelt and H. M. Mulder. Distance-hereditrary graphs.

This class is the same as the $\Delta$-confluent graphs introduced by Eppstein, Goodrich, and Meng (Delta-confluent Drawings). It is easy to see that $\Delta$-confluent graphs are closed under the operations you allow (and a single vertex is $\Delta$-confluent). On the other hand, a $C_5$ in a $\Delta$-confluent drawing must use a $\Delta$-junction, since the tree-confluent graphs are all bipartite (see Hui, Pelsmajer, Schaefer, Stefankovic, Train Tracks and Confluent Drawings). But then there must be either two branches of the $\Delta$-junction each containing two vertices of the $C_5$ or one branch that contains three vertices of the $C_5$. In either case, the $C_5$ must have two disjoint chords.

Eppstein, Goodrich, and Meng also prove that the $\Delta$-confluent graphs are the same as the distance-hereditary graphs, so the result follows from that.

This class is the same as the $\Delta$-confluent graphs introduced by Eppstein, Goodrich, and Meng (Delta-confluent Drawings). It is easy to see that $\Delta$-confluent graphs are closed under the operations you allow (and a single vertex is $\Delta$-confluent), and all $\Delta$-confluent graphs can be built using these operations (easy induction).

Eppstein, Goodrich, and Meng also prove that the $\Delta$-confluent graphs are the same as the distance-hereditary graphs, so the result follows from that.

Theorem 2 in the Eppstein, Goodrich, and Meng paper is the result tying distance-heredity to the operations you allow. It's attributed to a 1986 paper by H. Bandelt and H. M. Mulder. Distance-hereditrary graphs.

Titles of articles
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

This class is the same as the $\Delta$-confluent graphs introduced by Eppstein, Goodrich, and Meng (https://arxiv.org/abs/cs/0510024Delta-confluent Drawings). It is easy to see that $\Delta$-confluent graphs are closed under the operations you allow (and a single vertex is $\Delta$-confluent). On the other hand, a $C_5$ in a $\Delta$-confluent drawing must use a $\Delta$-junction, since the tree-confluent graphs are all bipartite (see Hui, Pelsmajer, Schaefer, Stefankovic, https://link.springer.com/article/10.1007/s00453-006-0165-xTrain Tracks and Confluent Drawings). But then there must be either two branches of the $\Delta$-junction each containing two vertices of the $C_5$ or one branch that contains three vertices of the $C_5$. In either case, the $C_5$ must have two disjoint chords.

Eppstein, Goodrich, and Meng also prove that the $\Delta$-confluent graphs are the same as the distance-hereditary graphs, so the result follows from that.

This class is the same as the $\Delta$-confluent graphs introduced by Eppstein, Goodrich, and Meng (https://arxiv.org/abs/cs/0510024). It is easy to see that $\Delta$-confluent graphs are closed under the operations you allow (and a single vertex is $\Delta$-confluent). On the other hand, a $C_5$ in a $\Delta$-confluent drawing must use a $\Delta$-junction, since the tree-confluent graphs are all bipartite (see Hui, Pelsmajer, Schaefer, Stefankovic, https://link.springer.com/article/10.1007/s00453-006-0165-x). But then there must be either two branches of the $\Delta$-junction each containing two vertices of the $C_5$ or one branch that contains three vertices of the $C_5$. In either case, the $C_5$ must have two disjoint chords.

Eppstein, Goodrich, and Meng also prove that the $\Delta$-confluent graphs are the same as the distance-hereditary graphs, so the result follows from that.

This class is the same as the $\Delta$-confluent graphs introduced by Eppstein, Goodrich, and Meng (Delta-confluent Drawings). It is easy to see that $\Delta$-confluent graphs are closed under the operations you allow (and a single vertex is $\Delta$-confluent). On the other hand, a $C_5$ in a $\Delta$-confluent drawing must use a $\Delta$-junction, since the tree-confluent graphs are all bipartite (see Hui, Pelsmajer, Schaefer, Stefankovic, Train Tracks and Confluent Drawings). But then there must be either two branches of the $\Delta$-junction each containing two vertices of the $C_5$ or one branch that contains three vertices of the $C_5$. In either case, the $C_5$ must have two disjoint chords.

Eppstein, Goodrich, and Meng also prove that the $\Delta$-confluent graphs are the same as the distance-hereditary graphs, so the result follows from that.

Source Link

This class is the same as the $\Delta$-confluent graphs introduced by Eppstein, Goodrich, and Meng (https://arxiv.org/abs/cs/0510024). It is easy to see that $\Delta$-confluent graphs are closed under the operations you allow (and a single vertex is $\Delta$-confluent). On the other hand, a $C_5$ in a $\Delta$-confluent drawing must use a $\Delta$-junction, since the tree-confluent graphs are all bipartite (see Hui, Pelsmajer, Schaefer, Stefankovic, https://link.springer.com/article/10.1007/s00453-006-0165-x). But then there must be either two branches of the $\Delta$-junction each containing two vertices of the $C_5$ or one branch that contains three vertices of the $C_5$. In either case, the $C_5$ must have two disjoint chords.

Eppstein, Goodrich, and Meng also prove that the $\Delta$-confluent graphs are the same as the distance-hereditary graphs, so the result follows from that.