{"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":"2021-11-20T18:53:46","modified_gmt":"2021-11-20T23:53:46","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":"

Carleton University
\nTechnical Report<\/a> TR-95-06
\nMarch\u00a01995<\/p>\n

Planar Stage Graphs: Characterizations and Applications<\/h2>\n
\n
\n
Frank Bauernoppel, Evangelos Kranakis,, Danny Krizanc, Anil Maheshwari, Jorg-Rudiger Sack, Jorge Urrutia<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n

We consider combinatorial and algorithmic aspects of the well-known paradigm \\killing two birds with one stone”. 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

TR-95-06.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-95-06 March\u00a01995 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”. We de\fne a stage graph as follows: vertices are the points from a planar […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11736,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-95-06: Planar Stage Graphs: Characterizations and Applications - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-95-06 March\u00a01995 Planar Stage Graphs: Characterizations and Applications Frank Bauernoppel, Evangelos Kranakis,,\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/\",\"name\":\"TR-95-06: Planar Stage Graphs: Characterizations and Applications - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-20T23:53:46+00:00\",\"dateModified\":\"2021-11-20T23:53:46+00:00\",\"description\":\"Carleton University Technical Report TR-95-06 March\u00a01995 Planar Stage Graphs: Characterizations and Applications Frank Bauernoppel, Evangelos Kranakis,,\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1995\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-95-06: Planar Stage Graphs: Characterizations and Applications\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-95-06: Planar Stage Graphs: Characterizations and Applications - School of Computer Science","description":"Carleton University Technical Report TR-95-06 March\u00a01995 Planar Stage Graphs: Characterizations and Applications Frank Bauernoppel, Evangelos Kranakis,,","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/","name":"TR-95-06: Planar Stage Graphs: Characterizations and Applications - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-20T23:53:46+00:00","dateModified":"2021-11-20T23:53:46+00:00","description":"Carleton University Technical Report TR-95-06 March\u00a01995 Planar Stage Graphs: Characterizations and Applications Frank Bauernoppel, Evangelos Kranakis,,","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-06-planar-stage-graphs-characterizations-and-applications\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1995","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/"},{"@type":"ListItem","position":5,"name":"TR-95-06: Planar Stage Graphs: Characterizations and Applications"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12768"}],"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\/49"}],"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"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}