Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine

DOI10.1137/S0895480195280319MaRDI QIDQ4699162zbMATH OpenOpenAlexWikidataFDO

Authors Hikoe Enomoto, Miki Shimabara Miyauchi

Publication date 23 November 1999

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480195280319

zbMATH Keywords

graphsbook embeddingcrossings of edges over the spine

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• A trade-off between page number and page width of book embeddings of graphs
• scientific article; zbMATH DE number 4049089
• Optimum embedding of complete graphs in books
• Book embeddings of nonplanar graphs with small faces in few pages
• Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
• Embedding Outerplanar Graphs in Small Books
• Two-page book embedding of trees under vertex-neighborhood constraints
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• scientific article; zbMATH DE number 3914339
• scientific article; zbMATH DE number 969978

Cited in

(18)

• Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
• Characterisations and examples of graph classes with bounded expansion
• Universal sets of \(n\) points for one-bend drawings of planar graphs with \(n\) vertices
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Book embeddings and crossing numbers
• Simpler algorithms for testing two-page book embedding of partitioned graphs
• A survey on book-embedding of planar graphs
• Approximating the fixed linear crossing number
• Two-page book embedding of trees under vertex-neighborhood constraints
• Upward book embeddings of st-graphs
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• Relating graph thickness to planar layers and bend complexity
• Embeddability Problems for Upward Planar Digraphs
• ON EMBEDDING A GRAPH ON TWO SETS OF POINTS
• scientific article; zbMATH DE number 3914339 (Why is no real title available?)
• Drawing colored graphs on colored points
• Drawing colored graphs with constrained vertex positions and few bends per edge
• On exteriority notions in book embeddings and treewidth

This page was built for publication: Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine

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