Colored Point-Set Embeddings of Acyclic Graphs

DOI10.1007/978-3-319-73915-1_32MaRDI QIDQ4625132zbMATH OpenOpenAlexFDO

Authors Emilio Di Giacomo, Giuseppe Liotta, Alfredo Navarra, Leszek Gąsieniec

Publication date 20 February 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.09167

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require $Omega(n^{f}rac23)$ edges each having $Omega(n^{f}rac13)$ bends in the worst case. The lower bound holds even when the function that maps vertices to points is not a bijection but it is defined by a 3-coloring. In contrast, a constant number of bends per edge can be obtained for 3-colored paths and for 3-colored caterpillars whose leaves all have the same color. Such results answer to a long standing open problem.

Recommendations

• k-Colored Point-Set Embeddability of Outerplanar Graphs
• k-colored Point-set Embeddability of Outerplanar Graphs
• Colored simultaneous geometric embeddings and universal pointsets
• Embedding Graphs into Colored Graphs
• Simultaneous embedding of colored graphs
• Point-set embeddability of 2-colored trees
• 2-colored point-set embeddings of partial 2-trees
• 2-colored point-set embeddings of partial 2-trees
• scientific article; zbMATH DE number 3487493
• Publication:3470476

Cites work

• Colored Point-Set Embeddings of Acyclic Graphs
• Drawing colored graphs on colored points
• Drawing colored graphs with constrained vertex positions and few bends per edge
• Embedding planar graphs at fixed vertex locations
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• k-colored Point-set Embeddability of Outerplanar Graphs
• ON EMBEDDING A GRAPH ON TWO SETS OF POINTS
• Point-set embeddability of 2-colored trees
• The Hamiltonian Augmentation Problem and Its Applications to Graph Drawing

Cited in

(5)

• Simultaneous embedding of colored graphs
• On the curve complexity of 3-colored point-set embeddings
• Relating graph thickness to planar layers and bend complexity
• Colored Point-Set Embeddings of Acyclic Graphs
• 2-colored point-set embeddings of partial 2-trees

This page was built for publication: Colored Point-Set Embeddings of Acyclic Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625132)