Beyond planar graphs : communications of NII Shonan meetings /: communications of NII Shonan meetings. ([2020])

• Record Type: Book
• Further Information: Note: Seok-Hee Hong, Takeshi Tokuyama, editors.
• Editors: Hong, Seok-Hee; Tokuyama, Takeshi
• Contents: Intro -- Preface -- Contents -- 1 Beyond Planar Graphs: Introduction -- 1.1 Beyond Planar Graphs: Edge Density -- 1.2 Computational Complexity: NP-Hardness -- 1.3 Polynomial-Time Testing Algorithm -- 1.4 Straight-Line Drawing -- 1.5 Outlook and Open Problem -- References -- 2 Quantitative Restrictions on Crossing Patterns -- 2.1 Introduction -- 2.2 Simple Graphs and Simple Topological Graphs -- 2.2.1 Simple Graphs Versus Multigraphs -- 2.2.2 t-Simple Topological Graphs -- 2.3 Overview of Graph Classes -- 2.4 Density -- 2.5 Inclusions -- 2.6 Recognition Algorithms -- 2.7 Open Problems 4.7 Difference from Optimal 1-Planar Graphs -- 4.8 Open Problems -- References -- 5 Algorithms for 1-Planar Graphs -- 5.1 Introduction -- 5.2 Testing Maximal 1-Planarity -- 5.3 Testing Outer-1-Planarity -- 5.4 Straight-Line Drawing Algorithm for 1-Planar Graphs -- 5.5 Recent Progress -- References -- 6 Edge Partitions and Visibility Representations of 1-planar Graphs -- 6.1 Introduction -- 6.2 Basic Definitions and Notation -- 6.3 Recognition and Structural Properties of 1-planar Graphs -- 6.4 Edge Partitions of 1-plane Graphs -- 6.4.1 Summary of Results -- 6.4.2 A Glimpse of a Proof Technique 6.5 Visibility Representations of 1-plane Graphs -- 6.5.1 Rectangle and Ortho-Polygon Visibility Representations -- 6.5.2 A Glimpse of a Proof Technique -- 6.5.3 Further Results on Visibility Representations of 1-plane Graphs -- 6.6 Concluding Remarks and Open Problems -- References -- 7 k-Planar Graphs -- 7.1 Introduction -- 7.2 Examples of k-Planar Graphs with High Density -- 7.3 Density Results and Their Implications to the Crossing Lemma -- 7.3.1 Two Important Implications -- 7.4 Interesting Subclasses -- 7.5 Relationship with k-quasi-planarity -- References -- 8 Fan-Planar Graphs 8.1 Introduction -- 8.2 Examples of Dense Fan-Planar Graphs -- 8.3 Relationships with Other Classes of Beyond-Planar Graphs -- 8.4 Density Results -- 8.5 NP-Hardness Results -- 8.6 Algorithmic Results -- 8.7 Open Problems -- References -- 9 Right Angle Crossing Drawings of Graphs -- 9.1 Introduction -- 9.2 Basic Terminology and Properties -- 9.3 Edge Density -- 9.4 Testing and Drawing Algorithms -- 9.4.1 RAC Drawings with Bends -- 9.4.2 Straight-Line RAC Drawings -- 9.4.3 RAC Drawings of Planar Graphs -- 9.5 Inclusion Relationships with 1-Planar Graphs -- 9.6 Concluding Remarks -- References.
• Publisher Details: Singapore : Springer
• Publication Date: 2020
• Extent: 1 online resource (viii, 270 pages), illustrations
• Subjects: 511.5; Graph algorithms; Graph theory -- Data processing; Electronic books
• Languages: English
• ISBNs: 9789811565335; 9811565333
• Related ISBNs: 9811565325; 9789811565328; 9789811565328
• Notes: Note: Includes bibliographical references and index.; Note: References -- 3 Quasi-planar Graphs -- 3.1 Introduction -- 3.2 The Size of k-Quasi-planar Graphs -- 3.2.1 3- and 4-Quasi-planar Graphs -- 3.2.2 k-Quasi-planar Graphs for k ge5 -- 3.2.3 Restricted Drawings -- 3.2.4 Lower Bounds -- 3.3 Relationships with Other Classes of Graphs -- 3.3.1 Beyond-Planar Graphs -- 3.3.2 Complete Graphs -- 3.4 Computational Aspects of k-Quasi-planar Graphs -- References -- 4 1-Planar Graphs -- 4.1 Definition and Basic Results -- 4.2 Connectivity -- 4.3 Planarization -- 4.4 Edge Density -- 4.5 Minors and Subgraphs -- 4.6 Re-embeddings of 1-Planar Graphs.
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.