New results on rectilinear crossing numbers and plane embeddings | Zendy

Bienstock Daniel | Zendy; Dean Nathaniel | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

New results on rectilinear crossing numbers and plane embeddings

Author(s) -

Bienstock Daniel,

Dean Nathaniel

Publication year - 1992

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.3190160502

Subject(s) - combinatorics , mathematics , crossing number (knot theory) , bounded function , regular polygon , plane (geometry) , planar graph , generalization , degree (music) , graph , discrete mathematics , geometry , mathematical analysis , physics , intersection (aeronautics) , acoustics , engineering , aerospace engineering

We show that if a graph has maximum degree d and crossing number k , its rectilinear crossing number is at most O ( dk 2 ). Hence for graphs of bounded degree, the crossing number and the rectilinear crossing number are bounded as functions of one another. We also obtain a generalization of Tutte's theorem on convex embeddings of 3‐connected plane graphs. © 1929 John Wiley & Sons, Inc.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research