LEADER 12561nam 22007935 450 001 996466470603316 005 20230329170550.0 010 $a3-319-68705-0 024 7 $a10.1007/978-3-319-68705-6 035 $a(CKB)4340000000223463 035 $a(DE-He213)978-3-319-68705-6 035 $a(MiAaPQ)EBC6304931 035 $a(MiAaPQ)EBC5596143 035 $a(Au-PeEL)EBL5596143 035 $a(OCoLC)1010953513 035 $a(PPN)221251324 035 $a(EXLCZ)994340000000223463 100 $a20171101d2017 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aGraph-Theoretic Concepts in Computer Science$b[electronic resource] $e43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers /$fedited by Hans L. Bodlaender, Gerhard J. Woeginger 205 $a1st ed. 2017. 210 1$aCham :$cSpringer International Publishing :$cImprint: Springer,$d2017. 215 $a1 online resource (XIII, 440 p. 87 illus.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v10520 311 $a3-319-68704-2 327 $aIntro -- Preface -- Organization -- Contents -- Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions -- 1 Complex Networks and Random Graphs: A Motivation -- 2 Random Graphs and Real-World Networks -- 3 Random Graph Models as Null Models -- 3.1 Null Model 1: Uniform Random Graph -- 3.2 Null Model 2: Erdo?s-Re?nyi Random Graph with Fixed Number of Edges -- 3.3 Null Model 3: Fixing All Degrees and the Configuration Model -- 3.4 Small-World Properties of the Configuration Model -- 4 Extensions: Other Models -- References -- On Bubble Generators in Directed Graphs -- 1 Introduction -- 2 Preliminaries -- 3 The Bubble Generator -- 4 A Polynomial-Time Algorithm for Decomposing a Bubble -- 5 Conclusions and Open Problems -- References -- Critical Node Cut Parameterized by Treewidth and Solution Size is W[1]-Hard -- 1 Introduction -- 2 Preliminaries -- 3 W[1]-HardNess of SumCSP -- 4 W[1]-HardNess of CNC -- References -- Hierarchical Partial Planarity -- 1 Introduction -- 2 Preliminaries -- 3 Relationships to Other Planarity Problems -- 4 Biconnected Facial-Constrained Core Planarity -- 4.1 High-Level Description of the Algorithm -- 4.2 Detailed Description of the Algorithm -- 5 Open Problems -- References -- On the Relationship Between k-Planar and k-Quasi-Planar Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Edge Rerouting Operations and Proof Strategy -- 4 Removing Tangled (k+1)-Crossings -- 5 Removing Untangled (k+1)-Crossings -- 5.1 Obtaining (k+1)-Quasi-Planarity -- 5.2 Obtaining Simplicity -- 6 Conclusions and Open Problems -- References -- Extension Complexity of Stable Set Polytopes of Bipartite Graphs -- 1 Introduction -- 2 Rectangle Covers and Fooling Sets -- 3 An Improved Upper Bound -- 4 An Improved Lower Bound -- 5 A Small Rectangle Cover of the Special Entries -- References. 327 $aOn the Number of Labeled Graphs of Bounded Treewidth -- 1 Introduction -- 2 The Construction -- 2.1 Notation and Definitions -- 2.2 Description of the Construction -- 2.3 Bounding the Treewidth -- 3 Proof of the Main Result -- 3.1 Number of Constructible Triples (, F, N) -- 3.2 Bounding the Number of Duplicates -- 3.3 Choosing the Parameter s -- 4 Concluding Remarks and Further Research -- References -- Uniquely Restricted Matchings and Edge Colorings -- 1 Introduction -- 2 Approximation Algorithms for Bipartite Graphs -- 3 Upper Bounds on ur'(G) -- 4 Concluding Remarks -- References -- Defective Coloring on Classes of Perfect Graphs -- 1 Introduction -- 2 Preliminaries and Definitions -- 3 NP-Hardness on Cographs -- 4 Polynomial Time Algorithm on Trivially Perfect Graphs -- 5 Algorithms on Cographs -- 5.1 Algorithm for Small Deficiency -- 5.2 Algorithm for Few Colors -- 5.3 Sub-Exponential Time Algorithm -- 6 Split and Chordal Graphs -- 6.1 Hardness for Bounded Deficiency -- 6.2 Hardness for Bounded Number of Colors -- 6.3 A Dynamic Programming Algorithm -- 7 Conclusions -- References -- Token Sliding on Chordal Graphs -- 1 Introduction -- 2 Hardness Results -- 2.1 Split Graphs -- 2.2 Bipartite Graphs -- 3 Interval Graphs -- 3.1 Basic Facts on Independent Sets in Interval Graphs -- 3.2 Reachability -- 3.3 Connectivity -- References -- Computing Maximum Cliques in B2-EPG Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Typed Intervals and Projection Graphs -- 3.1 Typed Intervals -- 3.2 Projection Graphs -- 4 Maximum Clique in B2-EPG Graphs -- 4.1 Graphs with Z-Vertices -- 4.2 General B2-EPG Graphs -- 5 Colorings and -boundedness -- References -- Intersection Graphs of Rays and Grounded Segments -- 1 Introduction -- 2 Preliminaries -- 3 Cycle Lemma -- 4 Stretchability -- 5 Rays and Segments -- References -- On H-Topological Intersection Graphs. 327 $a1 Introduction -- 2 Recognition of T-Graphs -- 3 Recognition Hardness -- 4 Dominating Set -- References -- The Hardness of Embedding Grids and Walls -- 1 Introduction -- 2 Preliminaries -- 2.1 From Homomorphism to Colored Embedding -- 3 Frames and Skeletons -- 4 Conclusions -- References -- Approximately Coloring Graphs Without Long Induced Paths -- 1 Introduction -- 2 Algorithm -- 3 Hardness Result -- 4 Conclusion -- References -- New and Simple Algorithms for Stable Flow Problems -- 1 Introduction -- 2 Preliminaries -- 3 A Polynomial-Time Augmenting Path Algorithm for Stable Flows -- 4 Stable Flows with Restricted Intervals -- 4.1 Forced Edges -- 4.2 Forbidden Edges -- 5 Stable Multicommodity Flows -- 5.1 Problem Simplification -- 5.2 Integral Multicommodity Stable Flows -- References -- Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes -- 1 Introduction -- 2 Preliminaries -- 3 Partitioning 3-Partite Graphs -- 4 Applications of Our Technique -- References -- Finding Cut-Vertices in the Square Roots of a Graph -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contributions -- 2 Preliminaries -- 2.1 Squares and Powers of Graphs -- 2.2 Graph Decompositions -- 3 Basic Properties of the Atoms in a Square -- 4 Computation of the Cut-Vertices from the Square -- 4.1 Recognition of the Essential Cut-Vertices -- 4.2 Sufficient Conditions for Non Essential Cut-Vertices -- 5 Reconstructing the Block-Cut Tree of a Square Root -- 6 Application to Trees of Cycle-Powers -- 7 Conclusion -- References -- The Minimum Shared Edges Problem on Grid-Like Graphs -- 1 Introduction -- 2 Preliminaries -- 3 On Bounded and Holey Grids -- 3.1 Bounded Grids -- 3.2 Holey Grids -- 3.3 Manhattan-Like Acyclic Digraphs -- 4 The Nonexistence of Polynomial Kernels -- 5 Conclusion -- References -- Linearly -Bounding (P6,C4)-Free Graphs -- 1 Introduction. 327 $a2 Preliminaries -- 3 The Structure of (P6,C4)-Free Atoms -- 4 -Bounding (P6,C4)-Free Graphs -- 5 A 3/2-Approximation Algorithm -- References -- Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2 -- 1 Introduction -- 2 Preliminaries -- 3 Outerplanar Roots -- 3.1 Structural Lemmas -- 3.2 The Algorithm -- 4 Roots of Pathwidth at Most Two -- 5 Conclusions -- References -- Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Enumeration of Maximal Irredundant Sets for Chordal Graphs -- 4 Enumeration of Maximal Irredundant Sets for Interval Graphs -- 5 Conclusions -- References -- The Minimum Conflict-Free Row Split Problem Revisited -- 1 Introduction -- 2 Formulations in Terms of Branchings in Directed Acyclic Graphs -- 3 A Strengthening of Dilworth's Theorem and Its Connection to the MCRS Problem -- 3.1 A Min-Max Relation Strengthening Dilworth's Theorem -- 3.2 Connection with the MCRS Problem -- 4 (In)approximability Issues -- 4.1 Hardness Results -- 4.2 2-Approximating and via Laminar Set Families -- 4.3 Two Approximation Algorithms for Computing and -- 5 Conclusion -- References -- Drawing Planar Graphs with Few Geometric Primitives -- 1 Introduction -- 2 Trees with Segments on the Grid -- 3 Planar 3-Trees with Few Segments on the Grid -- 4 Maximal Outerplanar Graphs with Segments on the Grid -- 5 Triangulations and Planar Graphs with Circular Arcs -- References -- Mixed Dominating Set: A Parameterized Perspective -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm for MDS Parameterized by the Solution Size -- 4 Outline of Algorithm for MDS Parameterized by Treewidth -- 5 Lower Bounds -- 6 Conclusion -- References -- Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity -- 1 Introduction -- 1.1 Related Work. 327 $a1.2 Our Contribution -- 2 Preliminaries -- 2.1 MSO and Its Extensions -- 2.2 Treewidth and Neighborhood Diversity -- 3 Graphs of Bounded Neighborhood Diversity -- 4 XP Algorithm for MSOGL on Bounded Treewidth -- 4.1 CSP, MSO and Treewidth -- 4.2 CSP Instance Construction -- 5 Conclusions -- References -- Extending Partial Representations of Trapezoid Graphs -- 1 Introduction -- 2 Modular Decomposition and Transitive Orientations -- 3 Trapezoid Models -- 4 Extending Partial Representations of Trapezoid Posets -- 5 Extending Partial Representations of Trapezoid Graphs -- References -- On Low Rank-Width Colorings -- 1 Introduction and Main Results -- 2 Preliminaries -- 3 Powers of Sparse Graphs -- 4 Other Positive Results -- 5 Negative Results -- 6 Erdo?s-Hajnal property and -boundedness -- 7 Conclusions -- References -- On Strongly Chordal Graphs That Are Not Leaf Powers -- 1 Introduction -- 2 Preliminary Notions -- 3 Alternating Cycles and Quartets in Leaf Powers -- 4 Strongly Chordal Graphs That Are Not Leaf Powers -- 5 Hardness of Finding rq in Chordal Graphs -- 6 Conclusion -- References -- New Results on Weighted Independent Domination -- 1 Introduction -- 2 Preliminaries -- 2.1 Modular Decomposition -- 2.2 Antineighborhood Decomposition -- 3 WID in (P5,P5)-Free Graphs -- 3.1 Decomposition Scheme -- 3.2 Application to (P5,P5)-Free Graphs -- 4 WID in (P5, P3+P2)-Free Graphs -- 5 Concluding Remarks and Open Problems -- References -- The Parameterized Complexity of the Equidomination Problem -- 1 Introduction -- 2 Twin Relation -- 3 Properties of Twin Classes Regarding Equidomination -- 4 An XP Algorithm for the k-EQUIDOMINATION Problem -- 5 Reduction Rules -- 6 Main Results -- 7 Hereditarily Equidominating Graphs -- 8 Conclusion and Outlook -- References -- Homothetic Triangle Contact Representations -- 1 Introduction -- 2 Schnyder Woods. 327 $a3 The System of Linear Equations. 330 $aThis book constitutes the revised selected papers of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017, held in Eindhoven, The Netherlands, in June 2017. The 31 full papers presented in this volume were carefully reviewed and selected from 71 submissions. They cover a wide range of areas, aiming at connecting theory and applications by demonstrating how graph-theoretic concepts can be applied in various areas of computer science. Another focus is on presenting recent results and on identifying and exploring promising directions of future research.  . 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v10520 606 $aComputer science?Mathematics 606 $aDiscrete mathematics 606 $aAlgorithms 606 $aArtificial intelligence?Data processing 606 $aComputer graphics 606 $aGeometry 606 $aDiscrete Mathematics in Computer Science 606 $aAlgorithms 606 $aData Science 606 $aComputer Graphics 606 $aGeometry 615 0$aComputer science?Mathematics. 615 0$aDiscrete mathematics. 615 0$aAlgorithms. 615 0$aArtificial intelligence?Data processing. 615 0$aComputer graphics. 615 0$aGeometry. 615 14$aDiscrete Mathematics in Computer Science. 615 24$aAlgorithms. 615 24$aData Science. 615 24$aComputer Graphics. 615 24$aGeometry. 676 $a511.5 702 $aBodlaender$b Hans L$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aWoeginger$b Gerhard J$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996466470603316 996 $aGraph-Theoretic Concepts in Computer Science$92569248 997 $aUNISA