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

zbMATH Open1243.05066MaRDI QIDQ426901FDOQ426901

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

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

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

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)

Cited In (5)

• A faster polynomial-space algorithm for Max 2-CSP
• Planarization and fragmentability of some classes of graphs
• Title not available (Why is that?)
• 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)