Intravascular imaging using optical coherence tomography (OCT) is commonly used in interventional cardiology for proper diagnosis and surgical planning. OCT provides high-‐resolution images for detailed investigation of atherosclerosis induced thickening of the lumen wall resulting in arterial blockage and triggering mortality. However, the stochastic uncertainty associated with the appearance of speckles in OCT limits effective visual investigation over large volume of pullback data. Thus, clinicians face problems investigating subtle variations in the lumen topology associated with plaque vulnerability and onset of necrosis. Also, manually annotation of OCT volumes by expert is a tedious task. In this paper, we propose a framework for automatically segmenting the lumen boundary in IV-OCT with minimum time‐complexity. The framework uses OCT imaging physics based graph representation of signals and random walks image segmentation approaches. First, each OCT frame is modelled as a 4-connected graph and edge weights are assigned incorporating OCT signal attenuation physics models. Second, optical backscattering maxima is tracked along each A-scan of OCT and is subsequently refined using global gray‐level statistics and used for initializing seeds. This automates the seed selection process thus avoiding manual interaction. Finally, lumen boundary is segmented using the random walks image segmentation using the initialized seeds. Accuracy of lumen segmentation has been measured on 15 in vitro and 6 in vivo pullbacks each with 150-200 frames using Cohen’s kappa coefficient (0.9786 ± 0.0061) measured with respect to cardiologist’s annotation. High segmentation accuracy substantiates the characteristics of this method to reliably segment lumen across pullbacks in presence of vulnerability cues and necrotic pool, and has a deterministic finite time‐complexity. This paper in general also illustrates development of methods and framework for tissue classification and segmentation incorporating cues of tissue-energy interaction physics in imaging.