{"id":12768,"date":"2021-11-20T18:53:46","date_gmt":"2021-11-20T23:53:46","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12768"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-95-06-planar-stage-graphs-characterizations-and-applications","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/","title":{"rendered":"TR-95-06: Planar Stage Graphs: Characterizations and Applications"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-95-06: Planar Stage Graphs: Characterizations and Applications\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/\">Technical Report<\/a> TR-95-06<br>\nMarch&nbsp;1995<\/p>\n\n\n\n<h2 id=\"planar-stage-graphs-characterizations-and-applications\" class=\"wp-block-heading tr_t1\">Planar Stage Graphs: Characterizations and Applications<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">Frank Bauernoppel, Evangelos Kranakis,, Danny Krizanc, Anil Maheshwari, Jorg-Rudiger Sack, Jorge Urrutia<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n\n\n\n<p>We consider combinatorial and algorithmic aspects of the well-known paradigm \\killing two birds with one stone&#8221;. We de\fne a stage graph as follows: vertices are the points from a planar point set, and fu; vg is an edge if and only if the (in\fnite, straight) line segment joining u to v inter- sects a given line segment, called a stage. We show that a graph is a stage graph if and only if it is a permutation graph. The characterization results in a compact linear space representation of stage graphs. This has been exploited for designing improved algorithms for matching in permutation graphs, two processor task scheduling for dependency graphs known to be permutation graphs, and dominance related problems for planar point sets.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-95-06.pdf\">TR-95-06.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-95-06 March&nbsp;1995 Planar Stage Graphs: Characterizations and Applications Frank Bauernoppel, Evangelos Kranakis,, Danny Krizanc, Anil Maheshwari, Jorg-Rudiger Sack, Jorge Urrutia Abstract We consider combinatorial and algorithmic aspects of the well-known paradigm \\killing two birds with one stone&#8221;. We de\fne a stage graph as follows: vertices are the points from a planar [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11736,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-12768","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12768","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12768"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12768\/revisions"}],"predecessor-version":[{"id":12769,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12768\/revisions\/12769"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11736"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12768"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12768"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}