Improved upper bounds for planarization and series-parallelization of degree-bounded graphs

MaRDI QIDQ426901zbMATH OpenFDO

Authors Keith Edwards, Graham Farr

Publication date 12 June 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i2p25

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

planarizationregular expressionfragmentabilityseries-paralleltree width

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Connectivity (05C40)

Recommendations

• Planarization and fragmentability of some classes of graphs
• Fragmentability of graphs
• Series parallel digraphs with loops
• scientific article; zbMATH DE number 5999572
• The maximum degree of series-parallel graphs

Cited in

(5)

• A faster polynomial-space algorithm for Max 2-CSP
• Planarization and fragmentability of some classes of graphs
• scientific article; zbMATH DE number 6254006 (Why is no real title available?)
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• \(K_4\)-minor-free induced subgraphs of sparse connected graphs

This page was built for publication: Improved upper bounds for planarization and series-parallelization of degree-bounded graphs

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